问题描述
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入格式
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式
输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678.
123.46758
123.46758
样例输出
3
样例输入
13524678.
46758123.
46758123.
样例输出
22
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #include<queue> 7 #include<set> 8 #define N 20005 9 using namespace std; 10 11 char mp[3][3], gp[3][3]; 12 int dir[4][2] = {0,1, 1,0, -1,0, 0,-1}; 13 char str[10]; 14 struct node{ 15 int x, y; 16 int step; 17 char cur_mp[3][3];//记录当前图案 18 node(){ 19 } 20 node(int x, int y, int step){ 21 this->x = x; 22 this->y = y; 23 this->step = step; 24 } 25 }; 26 set<int>st; 27 queue<node>q; 28 bool check(node cur){ 29 for(int i=0; i<3; ++i) 30 for(int j=0; j<3; ++j) 31 if(cur.cur_mp[i][j] != gp[i][j]) 32 return false; 33 return true; 34 } 35 36 int cal(node cur){//每一次移动将会映射到一个不同的整数 37 int ss = 0; 38 for(int i=0; i<3; ++i) 39 for(int j=0; j<3; ++j) 40 if(cur.cur_mp[i][j] != '.') 41 ss = ss*10+(cur.cur_mp[i][j]-'0'); 42 else ss = ss*10+9; 43 return ss; 44 } 45 46 void bfs(){ 47 st.clear(); 48 if(!q.empty()) 49 st.insert(cal(q.front())); 50 while(!q.empty()){ 51 node cur = q.front(); 52 q.pop(); 53 if(check(cur)) { 54 cout<<cur.step<<endl; 55 return ; 56 } 57 58 for(int i=0; i<4; ++i){ 59 int xx = cur.x+dir[i][1]; 60 int yy = cur.y+dir[i][0]; 61 if(xx<0 || xx>2 || yy<0 || yy>2) continue; 62 node nt = node(xx, yy, cur.step+1); 63 memcpy(nt.cur_mp, cur.cur_mp, sizeof(cur.cur_mp)); 64 nt.cur_mp[cur.x][cur.y]^=nt.cur_mp[xx][yy]; 65 nt.cur_mp[xx][yy]^=nt.cur_mp[cur.x][cur.y]; 66 nt.cur_mp[cur.x][cur.y]^=nt.cur_mp[xx][yy]; 67 int val = cal(nt); 68 if(st.find(val) != st.end()) continue; 69 st.insert(val); 70 q.push(nt); 71 } 72 } 73 cout<<-1<<endl; 74 } 75 76 int main() { 77 while(cin>>str){ 78 int bx, by; 79 while(!q.empty()) q.pop(); 80 int len = 0; 81 for(int i=0; i<3; ++i) 82 for(int j=0; j<3; ++j){ 83 mp[i][j] = str[len++]; 84 if(mp[i][j] == '.') bx=i, by=j; 85 } 86 node cur = node(bx, by, 0); 87 memcpy(cur.cur_mp, mp, sizeof(mp)); 88 q.push(cur); 89 cin>>str; 90 len = 0; 91 for(int i=0; i<3; ++i) 92 for(int j=0; j<3; ++j) 93 gp[i][j] = str[len++]; 94 bfs(); 95 } 96 return 0; 97 }
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/4345489.html，如需转载请自行联系原作者
