~~~~
题目链接:http://poj.org/problem?id=3221
显然是BFS找最优解,可是终止条件不好写,看到有一只队交上去一直TLE。
比赛完了看题解原来是以目标状态为起点,BFS给每个状态打表,用一个map映射存起来。
~~~~
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<string> #include<queue> #include<map> using namespace std; char str[10]; char s[10]="0123456"; map<string,int> v; //状态映射 map<string,int>ans; //答案映射 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<node> 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; }
POJ 3221 Diamond Puzzle.,布布扣,bubuko.com
原文:http://blog.csdn.net/darwin_/article/details/38489493