~~~~

题目链接：http://poj.org/problem?

id=3221

显然是BFS找最优解。但是终止条件不好写。看到有一仅仅队交上去一直TLE。

比赛完了看题解原来是以目标状态为起点，BFS给每一个状态打表。用一个map映射存起来。

~~~~

#include
#include
#include
#include
#include
#include
#include

char str[10];
char s[10]="0123456";
map v; //状态映射
mapans; //答案映射
struct node
{
int t;
char s[10];
};
//分别在0~6位置能够到达的目标位置，以-1结束。

int dir[7][4]={
{2,4,6,-1},{2,6,-1},{1,0,3,-1},{2,4,-1},
{3,0,5,-1},{4,6,-1},{1,0,5,-1} };
int Find(char* s)
{
for(int i=0;i<7;i++) if(s[i]=='0') return i; } int bfs() { queue q;
node cur,next;
strcpy(cur.s,s);cur.t=0;
q.push(cur);
v[cur.s]=1;
ans[cur.s]=0;
while(!q.empty())
{
cur=q.front(); q.pop();
int pos=Find(cur.s); //'0'的位置。

for(int i=0;dir[pos][i]!=-1;i++)
{
char temp[10];
strcpy(temp,cur.s);
//交换‘0’和和对应能去的位置
swap(temp[pos],temp[dir[pos][i]]);
if(!v[temp])
{
v[temp]=1;
strcpy(next.s,temp);
next.t=cur.t+1;
ans[next.s]=next.t;
q.push(next);
}
}
}
}
int main()
{
v.clear();
ans.clear();
bfs();
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",str);
if(strcmp(str,s)==0) puts("0");
else printf("%d\n",ans[str]==0?-1:ans[str]);
}
return 0;
}