【題目描述】

在一個 4×4 的方框內擺放了若干個相同的玩具，某人想將這些玩具重新擺放成為他心中理想的狀態(tài)，規(guī)定移動時只能將玩具向上下左右四個方向移動，并且移動的位置不能有玩具，請你用最少的移動次數(shù)將初始的玩具狀態(tài)移動到目標狀態(tài)。

【輸入】

前四行表示玩具的初始狀態(tài)，每行 4 個數(shù)字 1 或 0，1 表示方格中放置了玩具，0 表示沒有放置玩具。

接著是一個空行。

接下來四行表示玩具的目標狀態(tài)，每行 4 個數(shù)字 1 或 0，意義同上。

【輸出】

一個整數(shù)，所需要的最少移動次數(shù)。

【輸入樣例】

1111

0000
1110
0010

1010
0101
1010
0101

【輸出樣例】

4

思路：與 棋盤游戲（信息學奧賽一本通-T1451）是同一個題

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;} LL quickMultPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;} LL quickPowMod(LL a,LL b,LL mod){ LL res=1; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1; } return res; } LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); } LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); } LL LCM(LL x,LL y){ return x/GCD(x,y)*y; } const double EPS = 1E-6; const int MOD = 1000000000+7; const int N = 1000+5; const int dx[] = {0,0,-1,1,1,-1,1,1}; const int dy[] = {1,-1,0,0,-1,1,-1,1}; using namespace std;struct Node {int val;int step;Node() {}Node(int val, int step) : val(val), step(step) {} }; int vis[65536 + 10]; void BFS(Node st, Node ed) {memset(vis, 0, sizeof(vis));queue<Node> Q;Q.push(st);while (!Q.empty()) {Node now = Q.front();Q.pop();if (now.val == ed.val) {cout << now.step << endl;return;}int val = now.val;int step = now.step;for (int i = 15; i >= 0; i--) { //從高到低枚舉每一位int x = (15 - i) / 4, y = (15 - i) % 4; //橫縱坐標int nowPos = 1 << i; //當前位置代表權值int rightPos = 1 << (i - 1); //當前位置右方位置代表權值int downPos = 1 << (i - 4); //當前位置下方位置代表權值if (y < 3 && ((val & nowPos) != (val & rightPos))) { //向右交換int nextVal = val ^ nowPos ^ rightPos; //交換后的狀態(tài)if (!vis[nextVal]) {vis[nextVal] = true;Q.push(Node(nextVal, step + 1));}}if (x < 3 && ((val & nowPos) != (val & downPos))) { //向下交換int nextVal = val ^ nowPos ^ downPos; //交換后的狀態(tài)if (!vis[nextVal]) {vis[nextVal] = true;Q.push(Node(nextVal, step + 1));}}}} } int main() {char ch;int st = 0, ed = 0;for (int i = 15; i >= 0; i--) {cin >> ch;if (ch == '1')st += 1 << i;}for (int i = 15; i >= 0; i--) {cin >> ch;if (ch == '1')ed += 1 << i;}if (st == ed)printf("0\n");elseBFS(Node(st, 0), Node(ed, 0));return 0; }

?

總結

以上是生活随笔為你收集整理的移动玩具（信息学奥赛一本通-T1453）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。