[蓝桥杯][历届试题]九宫重排

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出
输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678.
123.46758
样例输出
3

题解：
实现bfs主要有两部分：标记状态，维护队列。

1.标记状态。这一题，状态是一个9宫格，我们标记图的状态的方法有hash，康拓展开式等等。这里我们利用unordered_map(hash表) 的方法来标记图的状态，只不过在此之前，我们需要把这样的一个图变成字符串。

2.维护队列。这里我们需要同时记录图的字符串和已经移动了多少步数，所以我们利用make_pair()来将string和step一起放到队列中去。

同时我们也总结一个bfs的模版

bool visit[N];
void bfs(int begin) {
    queue<node >que;
    fill(visit, visit + N, false);
    
    visit[begin] = true;
    que.push(begin);
    while(!que.empty()) {
        node top = que.front;
        que.pop();
        if(结束条件 ){
            输出结果
        }
        for(int i = 1; i < n; i++){
            枚举可能方向，位置
            注意状态的还原和记录
        }
    }
}

代码如下

#include<iostream>
#include<unordered_map>
#include<queue>
#include<cstring>

using namespace std;
unordered_map<string, bool>Hash; //hash标记 放在全局变量 初始为false
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
string To_string(char** m) {
    string s;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            s += m[i][j];
        }
    }
    return s;
}
char** to_map(string s) {
    char** map = new char *[3];
    for (int i = 0; i < 3; i++) {
        map[i] = new char[3];
    }
    for (int i = 0; i < s.length(); i++) {
        map[i / 3][i % 3] = s[i];
    }
    return map;
}
void Swap(char* a, char* b) {
    char tem = *a;
    *a = *b;
    *b = tem;
}
void bfs(string s, string e) {
    queue<pair<string, int>>que; //bfs队列
    Hash[s] = true;
    que.push(make_pair(s, 0));
    
    while(!que.empty()) {
        pair<string, int>top = que.front();
        int step = top.second;
        string string_map = top.first;
        que.pop();
        if(string_map == e) {
            cout << step;
            return;
        }
        char** map = to_map(string_map);
        int x = 0, y = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(map[i][j] == '.') {
                    x = i;
                    y = j;
                }
            }
        }
        for(int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(tx < 0 || tx > 2 || ty < 0 || ty > 2) {
                continue;
            }
            Swap(&map[tx][ty], &map[x][y]);
            string tems = To_string(map);
            if (Hash[tems] == true) {
                Swap(&map[tx][ty], &map[x][y]);
                continue;
            }
            Hash[tems] = true;
            que.push(make_pair(tems, step + 1));
            Swap(&map[tx][ty], &map[x][y]);
        }
    }
    cout << -1;
    return ;
}
int main() {
    string start, End;
    cin >> start >> End;
    bfs(start, End);
    return 0;
}

类似题目：
https://blog.****.net/caipengbenren/article/details/88071133