最小步数模型

介绍

1. 与一般BFS求地图内部最短距离不同，最小步数模型是要求图从开始状态经过状态改变到达最终状态的最小值。
2. 往往需要存储地图的状态，一般会采用哈希表

代码思路

整体思路：
    首先用哈希表存放到达某个状态的最短步数，如果题目需要输出方案还需一个哈希表记录某个状态的上一个状态。
    利用bfs逐个进行状态改变，某个状态如果dist为0，则说明未出现过，我们进行一系列操作并将它放入队列。
    如果状态改变到最终状态则直接return即可。

题目应用

1107. 魔板（算法提高课）

1107. 魔板

思路：

题目要求按照字典序最小，那我们就按照A、B、C的状态改变来进行BFS。
经过BFS后就可以得到两个哈希表的信息。
由于要输出方案，所以我们需要从最终状态开始遍历，不断获取钱一个状态，再将答案翻转即可。

代码：

#include <bits/stdc++.h>

using namespace std;

char g[2][4];
unordered_map<string, int> dist;
unordered_map<string, pair<char, string>> pre;

void set_s(string s)
{
    for(int i = 0; i < 4; i ++) g[0][i] = s[i];
    for(int i = 3, j = 4; i >= 0; i --, j++) g[1][i] = s[j];  
}

string get()
{
    string res;
    for(int i = 0; i < 4; i ++) res += g[0][i];
    for(int i = 3; i >= 0; i --) res += g[1][i];
    return res;
}

string move0(string s)
{
    set_s(s);
    for(int i = 0; i < 4; i++) swap(g[0][i], g[1][i]);
    return get();
}

string move1(string s)
{
    set_s(s);

    char t1 = g[0][3], t2 = g[1][3];
    for(int i = 3; i > 0; i --)
    {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    g[0][0] = t1, g[1][0] = t2;

    return get();
}

string move2(string s)
{
    set_s(s);

    char t = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = t;

    return get();
}

void bfs(string start, string end)
{
    if(start == end) return ;

    queue<string> q;
    dist[start] = 0;
    q.push(start);

    while(q.size())
    {
        string t = q.front();
        q.pop();

        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);

        for(int i = 0; i < 3; i++)
        {
            if(dist.count(m[i])) continue;

            dist[m[i]] = dist[t] + 1;
            pre[m[i]] = {i + 'A', t};
            q.push(m[i]);

            if(m[i] == end) return ;

        }
    }
}

int main()
{
    string start, end;
    for(int i = 0; i < 8; i++)
    {
        int x;
        cin >> x;
        end += char(x + '0');
    }

    start = "12345678";

    bfs(start, end);

    cout << dist[end] << endl;

    string res;
    while(end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }

    reverse(res.begin(), res.end());

    if(res.size() > 0) cout << res << endl;

    return 0;

}

845. 八数码（算法基础课）

845. 八数码
这道题比上一道题还要简单一点，因为只需要求最小步数，直接套用最小步数模型即可。
要注意状态的改变方式以及字符串和二维数组的转换。

#include <bits/stdc++.h>

using namespace std;

char g[3][3];
unordered_map<string, int>dist;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void set_s(string s)
{
    int cnt = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            g[i][j] = s[cnt ++];
}

string get()
{
    string res;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            res += g[i][j];

    return res;
}

int bfs(string start, string end)
{
    queue<string> q;
    dist[start] = 0;
    q.push(start);

    while(q.size())
    {
        string tmp = q.front();
        q.pop();

        set_s(tmp);

        int x, y;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                if(g[i][j] == 'x')
                    x = i, y = j;

        for(int i = 0; i < 4; i++)
        {
            set_s(tmp);
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue;

            swap(g[nx][ny], g[x][y]);

            string t = get();

            if(dist.count(t)) continue;
            dist[t] = dist[tmp] + 1;
            q.push(t);
            if(t == end) return dist[t];

        }

    }
    return -1;

}

int main()
{
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            cin >> g[i][j];

    string start, end;

    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            start += g[i][j];

    end = "12345678x";

    int res = bfs(start, end);


    cout << res << endl;

    return 0;
}