本文主要是介绍AcWing845.八数码问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

小技巧

一维数组下标转二位数组下标

//一维数组种下标k转化为n行m列的数组的下标变化
A[k]=B[k/n][k%m];
//逻辑上的转换，二维数数组本质上还是在内存种连续存储的
//此操作可以不转化一维数组为二维数组，对数组进行二维逻辑上的操作

//队列先进先出，队列前面的元素比后面元素的d值要小，所以第一次出现t==end时d[t]值就是最短路
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<unordered_map>
using namespace std;
const int N = 1e2 + 10;
typedef pair<int, int>PII;
int n, m;
queue<string>q;
unordered_map<string, int>d;
int bfs(string start)
{
    string end = "12345678x";
    int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };//上下左右四个bfs方向
    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 a = k / 3, b = k % 3;
        for (int i = 0; i < 4; i++)
        {
            int x = a + dx[i], y = b + dy[i];//转化为二维坐标以便判断是否越界
            if (x >= 0 && x < 3 && y >= 0 && y >= 0 && y < 3)
            {
                swap(t[k], t[x * 3 + y]);//交换两个字符，产生一个状态
                if (!d.count(t))//如果该状态第一次出现
                {
                    d[t] = distance + 1;//原状态变成新状态路径加一
                    q.push(t);//将新状态入队
                }
                swap(t[k], t[x * 3 + y]);//恢复原状态，来向其他方向进行bfs
            }
        }
    }
    return -1;
}

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

这篇关于AcWing845.八数码问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！