算法刷题笔记 八数码（C++实现）

题目描述

• 在一个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先后与右、下、右三个方向的数字交换成功得到正确排列。
• 现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式

• 输入占一行，将3×3的初始网格描绘出来。
• 例如，如果初始网格如下所示：

1 2 3
x 4 6
7 5 8

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

输出格式

• 输出占一行，包含一个整数，表示最少交换次数。
• 如果不存在解决方案，则输出−1。

基本思路

• 本题可以基于广度优先算法进行求解。对于数码的每一种摆放，我们可以将其视为一种状态，对应于一个图中的某一个结点。通过x和相邻元素的交换可以转移到另一个结点。那么，现在问题就变为，如何从开始状态的结点走到表示最终状态的结点。
• 由于每一次x与相邻元素发生交换后的状态是可以枚举出来的，因此可以采用广度优先搜索算法进行求解。每找出一种新的状态，就记录从初始状态到当前状态所需的转换次数。

实现代码

#include <iostream>
#include <queue>
#include <unordered_set>
#include <algorithm>
using namespace std;

// 用一个结构体来定义每一个状态的数码排列和离初始状态的距离
struct digital_state
{
    string current;
    int distance;
};

const string end_state = "12345678x";

int bfs(const string& start_state)
{
    // 创建一个用于记录状态的队列，并将开始状态放入队列中
    queue<digital_state> states;
    states.push({start_state, 0});
    // 创建一个哈希集合，存储已经出现过的状态，并将开始状态放入该集合中
    unordered_set<string> finded;
    finded.insert(start_state);
    // 通过循环找出从开始状态开始的所有不同状态，并计算其距离
    while(states.empty() == false)
    {
        // 取出队首元素
        digital_state temp = states.front();
        states.pop();
        // 如果队首元素对应的状态就是最终状态，则将该状态的距离返回
        if(temp.current == end_state) return temp.distance;
        // 队首元素对应的状态不是最终状态，则查找该状态的下一个可能状态
        else
        {
            // 首先确认字符x所在的位置，并将其转换为行和列
            int x_position = temp.current.find('x');
            int x_row = x_position / 3, x_col = x_position % 3;
            
            //判定x是否可以向上移动，如果可以则找到移动后的状态
            if(x_row >= 1)
            {
                string temp_state = temp.current;
                swap(temp_state[x_position], temp_state[x_position - 3]);
                // 如果该状态还未出现过，则记录该状态
                if(finded.find(temp_state) == finded.end())
                {
                    // 将该状态放入集合中
                    finded.insert(temp_state);
                    // 将该状态放入队列中
                    states.push({temp_state, temp.distance + 1});
                }
            }
            //判定x是否可以向下移动，如果可以则找到移动后的状态
            if(x_row <= 1)
            {
                string temp_state = temp.current;
                swap(temp_state[x_position], temp_state[x_position + 3]);
                // 如果该状态还未出现过，则记录该状态
                if(finded.find(temp_state) == finded.end())
                {
                    // 将该状态放入集合中
                    finded.insert(temp_state);
                    // 将该状态放入队列中
                    states.push({temp_state, temp.distance + 1});
                }
            }
            //判定x是否可以向左移动，如果可以则找到移动后的状态
            if(x_col >= 1)
            {
                string temp_state = temp.current;
                swap(temp_state[x_position], temp_state[x_position - 1]);
                // 如果该状态还未出现过，则记录该状态
                if(finded.find(temp_state) == finded.end())
                {
                    // 将该状态放入集合中
                    finded.insert(temp_state);
                    // 将该状态放入队列中
                    states.push({temp_state, temp.distance + 1});
                }
            }
            //判定x是否可以向右移动，如果可以则找到移动后的状态
            if(x_col <= 1)
            {
                string temp_state = temp.current;
                swap(temp_state[x_position], temp_state[x_position + 1]);
                // 如果该状态还未出现过，则记录该状态
                if(finded.find(temp_state) == finded.end())
                {
                    // 将该状态放入集合中
                    finded.insert(temp_state);
                    // 将该状态放入队列中
                    states.push({temp_state, temp.distance + 1});
                }
            }
        }
    }
    // 不存在解决方案的情况
    return -1;
}

int main(void)
{
    string start_state;
    for(int i = 0; i < 9; ++ i) 
    {
        char c;
        cin >> c;
        start_state.push_back(c);
    }
    cout << bfs(start_state);
    return 0;
}