BFS信息学一本通（1451:棋盘游戏）

棋盘游戏。在一个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;
}