最小步数模型——AcWing 1107. 魔板

最小步数模型

定义

最小步数模型通常是指在某种约束条件下，寻找从初始状态到目标状态所需的最少操作或移动次数的问题。这类问题广泛存在于算法、图论、动态规划、组合优化等领域。具体来说，它涉及确定一个序列或路径，使得按照特定规则执行一系列步骤后，能够从起始位置或状态转换到目标位置或状态，且所花费的步骤尽可能少。

运用情况

1. 图的最短路径问题：如Dijkstra算法、Floyd-Warshall算法等，用于寻找两点间经过边的最小权重和，即最少步数。
2. 迷宫问题：寻找从起点到终点的最短路径，每步只能上下左右移动。
3. 跳台阶问题：一个人可以1步或2步上楼梯，求n阶楼梯有多少种不同的上法，也是求最小步数的一个变体。
4. 爬楼梯问题：每次可以爬1阶或2阶，求达到n阶楼梯的最少步数，考虑动态规划解法。
5. 状态转换问题：如编辑距离（将一个字符串转换为另一个字符串最少的插入、删除、替换操作次数）。

注意事项

1. 状态定义：明确问题中的状态如何表示，状态转移方程如何建立，这是解决问题的基础。
2. 边界条件：正确设定初始状态和目标状态，以及任何可能的限制条件，避免无限循环或错误解。
3. 避免重复计算：在动态规划等方法中，使用记忆化技术或递推公式减少重复子问题的计算。
4. 最优子结构：利用问题的最优子结构，即问题的最优解可以由其子问题的最优解组合得到。
5. 复杂度控制：考虑算法的时间和空间复杂度，选择合适的算法和数据结构以提高效率。

解题思路

1. 分析问题：明确问题的输入、输出及约束条件，识别问题的类型（如是否为最短路径、最优化问题等）。
2. 选择模型：根据问题特征选择合适的算法模型，如贪心、动态规划、图算法等。
3. 状态定义与转移：定义状态表示问题的某一阶段，构建状态转移方程，描述如何从一个状态转移到另一个状态。
4. 设计算法：依据状态转移方程设计算法，可能是递归、迭代、图的遍历等。
5. 实现与优化：编写代码实现算法，考虑边界条件和特殊情况处理，优化算法以降低时间和空间复杂度。
6. 验证与测试：通过测试用例验证算法的正确性，确保能正确处理各种边界条件和特殊情况。

AcWing 1107. 魔板

题目描述

AcWing 1107. 魔板 - AcWing

运行代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

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

void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];
    for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i];
}

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 state)
{
    set(state);
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);
    return get();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = 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] = v0, g[1][0] = v1;
    return get();
}

string move2(string state)
{
    set(state);
    int v = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = v;
    return get();
}

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

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

    while (!q.empty())
    {
        auto 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]))
            {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A' + i, t};
                q.push(m[i]);
                if (m[i] == end) return dist[end];
            }
    }

    return -1;
}

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

    for (int i = 1; i <= 8; i ++ ) start += char('0' + i);

    int step = bfs(start, end);

    cout << step << endl;

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

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

    if (step > 0) cout << res << endl;

    return 0;
}

代码思路

1. 状态表示：用一个长度为8的字符串表示矩阵的状态，前四位表示第一行，后四位逆序表示第二行。
2. 状态转换：定义了三种状态转换函数move0、move1和move2，分别对应三种操作。
3. 广度优先搜索：使用BFS从初始状态开始搜索，利用一个队列来存储待探索的状态，一个哈希表dist记录每个状态到初始状态的最小步数，另一个哈希表pre记录每个状态的前驱状态和对应的操作。
4. 路径回溯：当找到目标状态时，通过pre哈希表回溯并构造出从初始状态到目标状态的操作序列。

改进思路

1. 减少空间消耗：使用迭代而非递归来保存路径，可以减少递归调用栈的空间消耗。
2. 剪枝：在BFS过程中，可以添加剪枝策略，如遇到已经访问过且步数更优的状态时直接跳过，避免重复探索。
3. 输入验证：在读取目标状态时增加输入验证，确保输入是合法的（例如，确保是0和1组成，且0和1的数量符合要求）。
4. 优化状态表示：直接使用整型或位操作来表示状态，可能在某些情况下减少内存使用和加快状态比较速度。
5. 清晰的函数命名和注释：增加函数和关键变量的注释，使代码更易于理解和维护。