首页 > 代码库 > [Uva 10085] The most distant state (BFS)
[Uva 10085] The most distant state (BFS)
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1026
题目大意：就是说给你一个8数码，问你能够达到的距离最远的状态是什么。
刚开始以为只要顺着一边走就行了，后来发现这样走可能最远到达的状态也能通过其他方式到达。
在这里WA了好多次。
应该把所有可能出现的情况全都枚举出来，然后判重。。
UVA也真是慢。。4s的代码跑了快4分钟。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <map> 7 #include <set> 8 #include <queue> 9 #include <string>10 using namespace std;11 typedef unsigned long long ull;12 13 const int B = 10;14 15 struct Node{16 int status[3][3];17 int h;18 int x,y;19 string route;20 };21 22 int T;23 int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};24 25 26 int main(){27 scanf("%d",&T);28 for(int t=1;t<=T;t++){29 Node s;30 s.h = 0;31 set<int> se;32 for(int i=0;i<3;i++){33 for(int j=0;j<3;j++){34 scanf("%d",&s.status[i][j]);35 s.h = s.h*10+s.status[i][j];36 if( s.status[i][j] == 0){37 s.x = i; s.y = j;38 }39 }40 }41 se.insert(s.h);42 // printf("%d\n",s.h);43 s.route = "";44 queue<Node> q;45 q.push(s);46 Node ans = s;47 bool fl = true;48 while(!q.empty()){49 Node tn = q.front(); q.pop();50 if( fl || ans.route.size()<tn.route.size()) ans = tn;51 for(int i=0;i<4;i++){52 Node t = tn;53 int dx = t.x+dir[i][0], dy = t.y+dir[i][1];54 if( dx<=2&&dx>=0&&dy<=2&&dy>=0 ){55 swap(t.status[tn.x][tn.y],t.status[dx][dy]);56 t.x = dx; t.y = dy;57 int tt = 0;58 for(int i=0;i<3;i++){59 for(int j=0;j<3;j++){60 tt = tt*B+t.status[i][j];61 }62 }63 t.h = tt;64 65 if( i==0 ) t.route = tn.route+"D";66 else if( i==1 ) t.route = tn.route+"U";67 else if( i==2 ) t.route = tn.route+"R";68 else if( i==3 ) t.route = tn.route+"L";69 if( se.find(tt)==se.end() ){70 se.insert(tt);71 q.push(t);72 }73 }74 }75 }76 printf("Puzzle #%d\n",t);77 for(int i=0;i<3;i++) for(int j=0;j<3;j++){78 printf(j==2?"%d\n":"%d ",ans.status[i][j]);79 }80 puts(ans.route.c_str());81 puts("");82 }83 return 0;84 }
[Uva 10085] The most distant state (BFS)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。