蓝桥杯历届试题-九宫重排C++ BFS+SET查重（目前本网站最简）

解题思路:
我不喜欢啰嗦的代码，我用二维数组来做会让代码变得啰嗦，所以我用一维数组，那么上下左右走的方向数组可以换为一维数组的{-3, -1, 1, 3}

结构体内的代码我只需要当前的状态state以及我到当前状态走的步数step

注意事项:

    如果我用一维数组的话，我需要判断我当前位置'.'的位置的合法性，如：我在3位置时我不能向左移动一步

因3是第二行第一个，向左移动会移动到第一行第三的位置，属于非法操作。

参考代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <cstdio>
#include <map>

#define LEN(array) ((sizeof(array)) / (sizeof(array[0])))
#define mo 1e9 + 7
#define ll long long int

using namespace std;

char mp[3][3];
string n, m;
int lr[] = {-3, -1, 1, 3};

struct node{
    string state;
    int step;
    node(string state, int step) : state(state), step(step){}
};


int main(void){
    int wz, res = 0;
    cin >> n >> m;
    set<string> s;
    queue<node> q;
    q.push({n, 0});

    while (!q.empty()){
        node now = q.front();
        q.pop();
        if (now.state == m){
            cout << now.step << endl;
            return 0;
        }
        wz = now.state.find(".");
        for (int i = 0; i < 4; i++){
            int new_wz = wz + lr[i];
            if ((wz == 3 && lr[i] == -1) || (wz == 5 && lr[i] == 1) || 
                (wz == 2 && lr[i] == 1) || (wz == 6 && lr[i] == -1)   ) {
                    new_wz = 0;
                    continue;
                }
            if (new_wz >= 0 && new_wz <= 9){
                string temp = now.state;
                swap(temp[wz], temp[new_wz]);
                if (!s.count(temp)){
                    q.push({temp, now.step + 1});
                    s.insert(temp);
                }
            }
        }
    }
    s.clear();
   
    return 0;
}