题目描述

在一个 3×3
的网格中，1∼8
这 8
个数字和一个 x 恰好不重不漏地分布在这 3×3
的网格中。

例如：

1 2 3
x 4 6
7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式
输入占一行，将 3×3
的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8

输出格式
输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1
。

样例

输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19

本蒟蒻第一篇题解，可能会有点唐QWQ（欢迎指出错误）。思路在注释里，非常基础，主要是为了照顾肖捧油。

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

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//变换方向 

int dfs(string start){
    string end = "12345678x";//记录最终状态 
    queue<string> q;//存储每个状态 
    unordered_map<string, int> d;//存储每个状态的距离 
    q.push(start);//初始状态 
    d[start] = 0;

    while(q.size()){
        auto t = q.front();//记录状态 
        q.pop();

        int distance = d[t];//记录距离 

        if(t == end) return distance;//终止条件 

        int k = t.find('x');//寻找当前'x'的下标
        int x = k/3, y = k%3;//将字符串转换成二维矩阵 

        for(int i = 0; i < 4; i++) //依次查找'x'周围四个位置 
        {
            int a = x+dx[i], b = y+dy[i];
            if(a >= 0 && a < 3 && b >= 0 && b < 3)//判断是否超格 
            {
                swap(t[a*3+b], t[k]);//交换原字符串中'x'与其周围的数 
                if(!d.count(t)) //d.count(t):哈希表d中't'对应的数 
                {
                    d[t] = distance+1;//若此状态没有出现过,则更新状态 
                    q.push(t);//可以理解为使循环继续 
                }
                swap(t[a*3+b], t[k]);//恢复状态 
            }
        }
    }
    return -1;
}

int main(){
    string start;
    for(int i = 0; i < 9; i++){
        char c;
        cin >> c;
        start += c;
    }
    cout << dfs(start) << endl;
    return 0;
}