八数码

在一个 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

输出样例

解析

题目要求最少步数，那么对于求最少步数这一类的问题我们可以考虑用宽搜来做，层层搜索后第一个搜到的就是符合要求的答案。

那么对于这道题目，我们先看一下题目的例子：

移动方式：

转以后：a = x + dx[i], b = y + dy[i].

思想：将每一种情况作为1个节点，目标情况即为终点

从初始状况移动到目标情况 —> 求最短路

问题：①如何记录每一个状态的“距离”（即需要移动的次数）？

②队列怎么定义，dist数组怎么定义？

解决方案：将二维数组转化为字符串

那么我们就需要思考一下二维数组坐标与一位数组坐标之间的相互转换

时间复杂度

一共9个字符，状态总数就相当于1~9的全排列，362880个，如果搜不出答案枚举所有状态不会TLE，为O( 9! )

代码（附注释）：

#include<iostream>
#include<cstring>
#include<queue>
#include <unordered_map>

using namespace std;

string s="12345678x"; //目标
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //四个方向坐标偏移量
unordered_map<string, int> d; //存放拓展出来的状态和对应的步数
queue<string> q;

int bfs(string start) {
    q.push(start);
    d[start] = 0; //初始状态为0步
    while(!q.empty()) {
        auto t = q.front();
        q.pop();
        if(s == t) return d[s]; //如果相同就提前结束，返回步数
        int k = t.find('x'); //找到x在一维数组的位置
        int x = k / 3, y = k % 3; //通过一维转化为二维数组坐标，因为已知矩阵为3*3
        for (int i = 0; i < 4; i ++ ) { //枚举四个方位
            int xx = x + dx[i], yy = y + dy[i]; //新坐标
            if(xx < 0 || xx >= 3 || yy < 0 || yy >= 3) continue; //越界则跳过
            int dis = d[t]; //交换前的步数
            swap(t[k], t[xx*3+yy]);
            //如果哈希表里没有，就从交换前的步数+1并放入队列
            if(!d.count(t)) d[t]=dis+1,q.push(t); 
            swap(t[k], t[xx*3+yy]); //恢复现场
        }
    }
    return -1;  //到达不了目标，返回题目要求的-1
}
int main() {
    string start; //初始状态
    for(int i = 0 ; i < 9; i ++) {
        char c;
        cin >> c;
        start += c;
    }
    cout << bfs(start) << endl;
    return 0;
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/118462.html