【c++基础】八数码难题

说明

在 3×3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。如果无解则输出-1；

输入数据

输入初始状态，一行九个数字，空格用 0 表示。

输出数据

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

如果无解则输出-1；

样例

输入样例

283104765

输出样例

4

样例解释

题解

# include <bits/stdc++.h>
#include <queue>
#include <variant>
using namespace std;
struct stru
{
    string st;
    int num,wt;
};
int wt,dir[]={0,3,-3,1,-1};
string str;
queue <stru> q;
map <string,bool> mp;
void bfs()
{
    q.push((stru){str,0,wt});
    mp[str]=1;
    while (!q.empty())
    {
        stru s=q.front();
        q.pop();
        if (s.st=="123804765")
        {
            cout<<s.num;
            return ;
        }
        for (int u=1;u<=4;u++)
        {
            int ux=dir[u]+s.wt;
            if (u==3||u==4)
                if (ux/3!=s.wt/3)
                    continue;
            if (ux>=0&&ux<=8)
            {
                swap(s.st[ux],s.st[s.wt]);
                if (!mp[s.st])
                {
                    mp[s.st]=1;
                    q.push((stru){s.st,s.num+1,ux});
                }
                swap(s.st[ux],s.st[s.wt]);
            }
        }
    }
    cout<<-1;
}
int main()
{
    cin>>str;
    for (int u=0;u<10;u++)
        if (str[u]=='0')
            wt=u;
    bfs();

    return 0;
}