JZ101-Eight-Puzzle

JZ101 八数码

#include<bits/stdc++.h>
using namespace std;
string a;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char dmove[4]={'u','d','l','r'};//按照udlr的顺序找的最短路径就必然是符合题意的,不用找到所有最短路径，bfs也无法找出所有最短路径
int c[100];
unordered_map<string,bool> mp;

struct node{
    string cur;//目前状态
    string ans;//走到cur状态的路径
};
node t;
string b;
queue<node>q;
int main(){
    cin >> a;
    int tot=0;
    for (int i=0;i<9;i++)
    {
        if (a[i]=='x') c[i+1]=0;
        else c[i+1]=a[i]-'0';
    }
    for (int i=1;i<9;i++)  
        for (int j=i+1;j<=9;j++)
        {
            if (c[i]==0 || c[j]==0) continue;
            if (i<j && c[i]>c[j]) tot++;
        }
    if (tot%2) //逆序数的奇偶性不同则不可能通过交换得到
    {   
        cout<<"unsolvable\n";
        return 0;
    }
    t.cur=a;
    t.ans="";
    q.push(t);
    int num,nnum,nx,ny;

    while(!q.empty())
    {
        node nt=q.front();
        num=nt.cur.find('x');
        for(int i=0;i<4;i++)//尝试向四个方向走
        {
            nx=num/3;
            ny=num%3;
            nx+=dx[i];
            ny+=dy[i];
            if (nx<0||nx>2||ny<0||ny>2) continue;//走法违规
            nnum=nx*3+ny;
            t=nt;
            t.cur[num]=t.cur[nnum];//进行移动
            t.cur[nnum]='x';
            t.ans+=dmove[i];
            if (mp[t.cur]==true) continue;
            mp[t.cur]=true;
            if (t.cur=="12345678x")//找到符合题意的最短路径即可输出最短路径并跳出循环
            {
                cout<<t.ans<<endl;
                return 0; 
            }
            q.push(t);
        }
        q.pop();
    }
    return 0;
}

事实上原始的BFS无法找出全部的最短路径，只能得到一个解。

原始的BFS算法在遇到已经访问过的状态时会跳过该状态，这可能导致某些分支被提前剪枝，无法搜索到所有解。它通过使用unordered_map来记录已访问的状态，保证每个状态只被访问一次，从而避免进入循环。此题如果将dx,dy,dmove数组中元素的值重排顺序，所输出的最短路径就不是按照udlr的优先顺序，就可能会得到不同的答案。