八数码(BFS解法)

题目链接

采用BFS思路解决八数码问题会遇到以下几个问题：

1. 如何表示八数码的一个状态？(string)
2. BFS所需的队列该如何表示？(queue)
3. BFS所需记录距离(这里也可视为移动步数)的dist数组该如何定义？(unordered_map<string, int>)

• 这里unordered_map(无序映射) 底层实现是哈希表

状态转移公式---从string数组转移到3x3矩阵

int x = k / 3, y = k % 3;

走向前后左右四个位置

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

代码部分

#include <bits/stdc++.h>

using namespace std;

int bfs(string start)
{
    // BFS所需的存储每一种状态的队列,以及到初始状态的dist数组
    queue<string> q;
    unordered_map<string, int> d;
    
    // 最终状态
    string end = "12345678x";
    
    // 初始化队列以及dist
    q.push(start);
    d[start] = 0;
    
    // 定义向上下左右移动的枚举数组
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1};
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        // 将字符串转换为矩形存储
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        
        int distance = d[t];
        
        if(t == end) return distance;
        
        for(int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[k], t[a * 3 + b]);
                // 判断该状态是否已经通过BFS走过
                if(!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    return -1;
}

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