八数码难题

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

283104765

样例输出 #1

4

提示

样例解释

图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

#include<bits/stdc++.h>
using namespace std;

//使用map来表示变化为当前的字符串需要的步数
map<string , int> dist;
//用来存放变化的字符串
queue<string> q;

//初始字符串和结束字符串
string start;
string end1 = "123804765";

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int bfs()
{
    dist[start] = 0;
    q.push(start);

    while(!q.empty())
    {
        auto t = q.front();

        q.pop();
        if(t == end1) return dist[t];
        int distance = dist[t];

        int a = t.find('0');

        //小技巧:一维数组下标转换为二维数组下标
        int x1 = a / 3;
        int y1 = a % 3;

        for(int i = 0; i < 4; i++)
        {
            int x2 = x1 + dx[i];
            int y2 = y1 + dy[i];

            if(x2 < 0 || y2 < 0 || x2 >= 3 || y2 >= 3) continue;

            //算出移动后0的二维坐标
            //再将二维坐标转换为一维坐标
            int tmp = x2 * 3 + y2;

            //改变0的位置
            swap(t[a],t[tmp]);

            //如果当前字符串在map中不存在
            if(dist.count(t) == 0)
            {
                dist[t] = distance + 1;
                q.push(t);
            }

            //恢复现场
            //使得0可以往其他方向再次移动
            swap(t[a],t[tmp]);
        }
    }
    return -1;
}

int main()
{
    cin>>start;

    int res = bfs();
    cout<<res<<endl;

    return 0;
}