棋盘游戏。在一个4 x 4的棋盘上有 8个黑棋和 8个白棋,当且仅当两个格子有公共边,这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。给出一个初始棋盘和一个最终棋盘,请找出一个最短的移动序列使初始棋盘变为最终棋盘。
- 输入:
前四行,每行4个数字( 1或者0 ),描述了初始棋盘;接着是一个空行; 第六到第九行,每行 4个数字( 1或者0),描述了最终棋盘。
- 输出:
输出的第一行是一个整数n,表示最少的移动步数。
C语言实现
棋盘游戏。在一个4 x 4的棋盘上有 8个黑棋和 8个白棋,当且仅当两个格子有公共边,这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。给出一个初始棋盘和一个最终棋盘,请找出一个最短的移动序列使初始棋盘变为最终棋盘。
前四行,每行4个数字( 1或者0 ),描述了初始棋盘;接着是一个空行;
第六到第九行,每行 4个数字( 1或者0),描述了最终棋盘。
输出的第一行是一个整数n,表示最少的移动步数。
C语言实现
#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; //交换后的状态
if (!vis[nextVal]) {
vis[nextVal] = true;
Q.push(Node(nextVal, step + 1));
}
}
if (x < 3 && ((val & nowPos) != (val & downPos))) { //向下交换
int nextVal = val ^ nowPos ^ downPos; //交换后的状态
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");
else
BFS(Node(st, 0), Node(ed, 0));
return 0;
}