129
uva 704 - Colour Hash map+双向bfs
这题从上周日开始想写的，结果拖了一周……现在写题效率越来越低了，要计时训练了。
一道很复杂的隐式图搜索……状态数有24位，看到网上有人按11进制转换，然后对Hash_MAX取模，个人认为这种做法不靠谱。于是把状态变成string类型的，直接用map，对于map，24位的string效率还是非常高的。
搜索的时候双向bfs，因为比较懒，所以把反向和正向写一起了，其实逆向只用做一次就可以了。
还有一点要注意的就是要输出数字最小的一种变换序号，这个处理方法就是把一层都搜索完，看到网上有人的代码完全没考虑，最后居然还过了，只能说数据水了……
输出逆向bfs时注意是逆变换。
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include<map>
#define INF 1E9
using namespace std;
const int Aim[24]={0,3,4,3,0,5,6,5,0,1,2,1,0,7,8,7,0,9,10,9,0,1,2,1};
string aim;
struct node
{
int c,flag,i;//c表示走过路程，flag-1为正向，2为逆向，i为操作序号
string fa;//父状态
};
string t;
string turn(string s,int num)//变换
{
string now;
switch(num)
{
case 1:now=s.substr(10,2)+s.substr(0,10)+s.substr(12,9);
now+=now.substr(9,3);return now;
case 3:now=s.substr(2,10)+s.substr(0,2)+s.substr(12,9);
now+=now.substr(9,3);return now;
case 4:now=s.substr(0,9)+s.substr(22,2)+s.substr(12,10);
now.insert(9,now.substr(18,3));return now;
case 2:now=s.substr(0,9)+s.substr(14,10)+s.substr(12,2);
now.insert(9,now.substr(18,3));return now;
default: return s;
}
}
string input()
{
int i,j;
string now="";
aim="";
for(i=0;i<24;i++)
{
scanf("%d",&j);
now.push_back(j);
aim.push_back(Aim[i]);
}
return now;
}
map<string,node> vis;
queue<string> q;
node next;
int out[20],no=0,nt,tt[20];
void output(string nn)//向前递归输出
{
if(vis[nn].fa=="-1")return;
output(vis[nn].fa);
tt[nt++]=vis[nn].i;
}
void print(string now,string t,int i)
{
nt=0;
if(vis[now].flag==2)swap(now,t);//判断前后遍历节点
output(now);//向前遍历
tt[nt++]=i;//中间
for(t;vis[t].fa!="-1";t=vis[t].fa)tt[nt++]=vis[t].i;//向后遍历
if(nt<no||no==0){no=nt;memcpy(out,tt,sizeof(tt));}//比大小
else if(nt>no)return;
for(i=0;i<nt&&out[i]==tt[i];i++);
if(out[i]>tt[i]){memcpy(out,tt,sizeof(tt));}
}
bool solve(string s)//双向bfs
{
if(s==aim){cout<<"PUZZLE ALREADY SOLVED"<<endl;return 1;}
vis.clear();
while(!q.empty())q.pop();
next.c=1;next.fa="-1";next.flag=1;next.i=0;vis[s]=next;
q.push(s);//正向起点
next.flag=2;vis[aim]=next;
q.push(aim);//逆向起点
bool flag=1;
string now;
int i,last;
while(!q.empty())
{
now=q.front();q.pop();
next.flag=vis[now].flag;
next.c=vis[now].c+1;
if(next.c>last&&!flag)break;//把这一层全遍历完，以确定最小值
next.fa=now;
if(next.c>9){cout<<"NO SOLUTION WAS FOUND IN 16 STEPS"<<endl;return 1;}
for(i=1;i<=4;i++)
{
if(next.flag==1) t=turn(now,i);
else t=turn(now,(i+1)%4+1);
next.i=i;
if(vis[t].c!=0)
if(vis[t].flag==next.flag)continue;
else {flag=0;print(now,t,i);break;}
q.push(t);vis[t]=next;
}
last=next.c;
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
string org;
while(T--)
{
no=0;
if(solve(input()))continue;
for(int i=0;i<no;i++) printf("%d",out[i]);
puts("");
}
}
最后更新：2017-04-02 00:06:53