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

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

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

解题思路：将本为题简单化，相当于空白格相当于起点，然后找到空白格从开始图的位置到最后目标图的位置且图中数字相同的最小步数。
首先需要寻找最小步数这个我们可以用BFS来实现，下面要考虑的就是如何判断当前所处的页面以前是否出现过，这里我借助一个map映射来标记是否这个界面已经被访问过。

#include <bits/stdc++.h>

using namespace std;

char start[5][5],goal[5][5];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
map<string,int> vis;
struct Node
{
    int x,y;
    long long step;
    char Map[5][5];
};
bool check(Node a)///判断这个图和目标图是否相同
{
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            if(a.Map[i][j]!=goal[i][j])
                return false;
    }
    return true;
}
bool visited(Node a)///判断这个局面是否出现过
{
    string s = "";
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            s += a.Map[i][j];
    }
    if(vis[s]>0)
        return false;
    vis[s]++;
    return true;
}
int bfs(int xx,int yy)///BFS寻找最少步数
{
    Node cur,nex;
    cur.x = xx;cur.y = yy;
    cur.step = 0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            cur.Map[i][j] = start[i][j];
    }
    queue<Node> Q;
    Q.push(cur);
    while(!Q.empty()){
        cur = Q.front();
        Q.pop();
        if(check(cur)){
            return cur.step;
        }
        for(int i=0;i<4;i++){
            nex.x = cur.x + dir[i][0];
            nex.y = cur.y + dir[i][1];
            for(int ii=1;ii<=3;ii++){
                for(int j=1;j<=3;j++)
                     nex.Map[ii][j]= cur.Map[ii][j];
            }
            nex.step = cur.step + 1;
            if(nex.x>=1&&nex.x<=3&&nex.y>=1&&nex.y<=3){
                swap(nex.Map[nex.x][nex.y],nex.Map[cur.x][cur.y]);///交换两个方格的位置；
                if(visited(nex)){
                    if(check(nex)){
                        return nex.step;
                    }
                    Q.push(nex);
                }
            }

        }
    }
    return -1;
}
int main()
{
    int xx,yy;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin>>start[i][j];
            if(start[i][j]=='.'){///记录空白格的位置
                xx=i;yy=j;
            }
        }
    }
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin>>goal[i][j];
        }
    }
    cout<<bfs(xx,yy)<<endl;;
    return 0;
}