题目描述

在一个 4×4 的棋盘上有 8 个黑棋和 8 个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。

移动棋子的规则是交换相邻两个棋子。

给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。

样例

blablabla

算法1

(bfs) $O(m*n^3)$

这个人比较懒，喜欢用stl，所以用了string来存状态，用hashmap存了距离

C++ 代码

#include<iostream>
#include<cstring>
#include<queue>
#include<unordered_map>
using namespace std;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};


int bfs(string begin, string end){
    if(begin == end) return 0;
    unordered_map<string, int> dist;
    dist[begin] = 0;
    queue<string> q;
    q.push(begin);
    while(q.size()){
        string line = q.front();
        q.pop();
        for(int i=0; i<4; i++)
            for(int j=0; j<4; j++)
                for(int k=0; k<4; k++){
                    string tmp = line;
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x<0 || x>=4 || y<0 || y>=4) continue;
                    swap(tmp[i*4+j], tmp[x*4+y]);
                    if(dist.count(tmp)) continue;
                    dist[tmp] = dist[line] + 1;
                    if(tmp == end) return dist[end];
                    q.push(tmp);
                }
    }
    return -1;
}


int main(){
    string line;
    string begin, end;
    for(int i=0; i<4; i++){
        cin >> line;
        begin += line;
    }
    for(int i=0; i<4; i++){
        cin >> line;
        end += line;
    }
    cout << bfs(begin, end) << endl;
    return 0;
}