Description
在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。
Input
前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空
行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。
Output
一个整数，所需要的最少移动次数。
Sample Input
1111
0000
1110
0010
0000
1110
0010
1010
0101
1010
0101
Sample Output
4
Solution
为什么省选会考八数码这种纸张题啊，关键我一开始还WA了一发，调了10分钟没看出来，最后无意中扫了一眼发现我continue直接跳过了还原状态的过程，e...e..excuse me???
为了方便判重，我们分2行联立成2个数存入map即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <bits/stdc++.h> using namespace std; #define rep(i,s,t) for(int i = s; i <= t; ++ i) const int dx[] = {0,0,1,-1}; const int dy[] = {1,-1,0,0}; struct node { int a[5][5], g; }st, ed; map<pair<int,int>,bool> mp; bool cmp(node a,node b) { rep(i,1,4) rep(j,1,4) if(a.a[i][j] != b.a[i][j]) return false; return true; } bool ok(int a,int b){return a < 1 || b < 1 || a > 4 || b > 4;} void bfs() { queue<node> q; node head, next; int cur1, cur2; q.push(st); while(!q.empty()) { head = q.front(); q.pop(); if(cmp(head,ed)) {printf("%d",head.g); return;} rep(i,1,4) rep(j,1,4) if(head.a[i][j]) { next = head; ++ next.g; rep(k,0,3) if(!ok(i+dx[k],j+dy[k]) && !next.a[i+dx[k]][j+dy[k]]) { swap(next.a[i][j],next.a[i+dx[k]][j+dy[k]]); cur1 = 0; rep(u,1,2) rep(v,1,4) cur1 = cur1*10+next.a[u][v]; cur2 = 0; rep(u,3,4) rep(v,1,4) cur2 = cur2*10+next.a[u][v]; if(mp[make_pair(cur1,cur2)]) { swap(next.a[i][j],next.a[i+dx[k]][j+dy[k]]); continue; } mp[make_pair(cur1,cur2)] = true; q.push(next); swap(next.a[i][j],next.a[i+dx[k]][j+dy[k]]); } } } } int main() { rep(i,1,4) rep(j,1,4) scanf("%1d",&st.a[i][j]); rep(i,1,4) rep(j,1,4) scanf("%1d",&ed.a[i][j]); int cur1, cur2; cur1 = cur2 = 0; rep(u,1,2) rep(v,1,4) cur1 = cur1*10+st.a[u][v]; rep(u,3,4) rep(v,1,4) cur2 = cur2*10+st.a[u][v]; mp[make_pair(cur1,cur2)] = true; bfs(); return 0; } |