九宫格拼图问题（BFS）

九宫格拼图问题就是在3*3的格子上摆放8张拼图，空出一个格子，玩家要借助这个空格上下左右移动完成拼图，求完成拼图最少要移动多少次

题目：ALDS1_13_B

其实这个问题可以看成是在移动空格，并且记录下经过的所有状态。

我们把九宫格按照下面的方式进行编号：

那么就可以用一个一维数组来存储这些格子。

设一维数组下标为a，对于x、y坐标，有如下关系：

x=a/3, y=a%3

然后就可以应用bfs来求解了。代码如下：

#include <bits/stdc++.h>
using namespace std;
#define N 3
#define N2 9
const int dx[] = {0, 0, -1, 1}; //分别对应上下左右移动
const int dy[] = {1, -1, 0, 0};
const string pth[] = {"u", "d", "l", "r"};

struct node
{
    string path = "";
    int f[N2];
    int space; //空格所在位置

    bool operator<(const node &p)const
    {
        for(int i=0;i<N2;++i)
        {
            if(f[i]==p.f[i])
                continue;
            return f[i]<p.f[i];
        }
        return false;
    }
};

bool is_target(node nd)
{
    for (int i = 0; i < 9; ++i)
    {
        if (nd.f[i] != i + 1)
            return false;
    }
    return true;
}

string bfs(node st)
{
    queue<node> Q;
    map<node, bool> mp;

    st.path = "";
    Q.push(st);
    mp[st] = true;
    node u, v;

    while (!Q.empty())
    {
        u = Q.front();
        Q.pop();

        if (is_target(u))
            return u.path;

        int sx = u.space / N;
        int sy = u.space % N;

        for (int i = 0; i < 4; ++i)
        {
            int tx = sx + dx[i];
            int ty = sy + dy[i];
            if (tx >= N || tx < 0 || ty >= N || ty < 0)
                continue;
            v = u;
            v.path += pth[i];
            swap(v.f[u.space], v.f[N * tx + ty]);
            v.space = N * tx + ty;

            if(!mp[v])
            {
                //确保没有存在过这条路径
                mp[v] = true;
                Q.push(v);
            }
        }
    }

    return "cannot_solve";
}

int main()
{
    node st;
    for (int i = 0; i < N2; ++i)
    {
        cin >> st.f[i];
        if (st.f[i] == 0)
        {
            st.space = i;
            st.f[i] = N2;
        }
    }
    string ans = bfs(st);
    if(ans!="cannot_solve")
        cout<<ans.length()<<endl;
}

转载请注明来源：https://www.longjin666.top/?p=1069

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~