华容道问题题解

问题分析

华容道问题的核心是在一个 $n \times m$ 的棋盘上，通过一个空白格子和若干可移动棋子，通过移动棋子（只能移动到空白格子），将指定棋子从初始位置移动到目标位置，求最少移动步数或判断不可行。

每次游戏的输入包括：

• 空白格子初始位置 $(\mathit{EX}, \mathit{EY})$
• 指定棋子初始位置 $(\mathit{SX}, \mathit{SY})$
• 目标位置 $(\mathit{TX}, \mathit{TY})$

算法思路

采用广度优先搜索（BFS） 求解，原因是BFS能保证找到最短路径（最少移动步数）。

状态表示

每个状态用四元组 $(\mathit{ex}, \mathit{ey}, \mathit{sx}, \mathit{sy})$ 表示：

• $(\mathit{ex}, \mathit{ey})$：空白格子当前位置
• $(\mathit{sx}, \mathit{sy})$：指定棋子当前位置

状态转移

对于每个状态，尝试向四个方向（上、下、左、右）移动空白格子：

1. 计算新空白位置 $(\mathit{nex}, \mathit{ney}) = (\mathit{ex} + \mathit{dx}[d], \mathit{ey} + \mathit{dy}[d])$，其中 $d$ 为方向索引
2. 若新位置合法（在棋盘内且不是固定棋子）：
   • 若新位置与指定棋子位置重合，则指定棋子移动到原空白位置，即 $(\mathit{nsx}, \mathit{nsy}) = (\mathit{ex}, \mathit{ey})$
   • 否则指定棋子位置不变，即 $(\mathit{nsx}, \mathit{nsy}) = (\mathit{sx}, \mathit{sy})$

终止条件

当指定棋子位置 $(\mathit{sx}, \mathit{sy})$ 等于目标位置 $(\mathit{TX}, \mathit{TY})$ 时，返回当前步数。

代码实现

核心数据结构

// 状态结构体
struct State {
    int ex, ey;  // 空白格子位置
    int sx, sy;  // 指定棋子位置
    int step;    // 当前步数
};

// 方向数组
const int dx[] = {1, -1, 0, 0};  // 上下左右
const int dy[] = {0, 0, 1, -1};

// 距离和访问标记数组
int dist[N][N][N][N];  // 记录到达状态的最小步数
bool vis[N][N][N][N];  // 标记状态是否已访问

BFS实现

int bfs(int ex, int ey, int sx, int sy, int tx, int ty) {
    // 初始化
    memset(vis, 0, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    queue<State> q;
    q.push({ex, ey, sx, sy, 0});
    vis[ex][ey][sx][sy] = true;
    dist[ex][ey][sx][sy] = 0;

    while (!q.empty()) {
        auto [ex, ey, sx, sy, step] = q.front();
        q.pop();

        // 找到目标
        if (sx == tx && sy == ty) return step;

        // 尝试四个方向移动
        for (int d = 0; d < 4; ++d) {
            int nex = ex + dx[d], ney = ey + dy[d];
            // 检查新空白位置合法性
            if (nex < 1 || nex > n || ney < 1 || ney > m || grid[nex][ney] == 0) 
                continue;

            // 计算新的指定棋子位置
            int nsx = sx, nsy = sy;
            if (nex == sx && ney == sy) {
                nsx = ex;
                nsy = ey;
            }

            // 访问新状态
            if (!vis[nex][ney][nsx][nsy] && step + 1 < dist[nex][ney][nsx][nsy]) {
                dist[nex][ney][nsx][nsy] = step + 1;
                vis[nex][ney][nsx][nsy] = true;
                q.push({nex, ney, nsx, nsy, step + 1});
            }
        }
    }
    // 无法到达目标
    return -1;
}

时间复杂度分析

• 状态总数：最多为 $n \times m \times n \times m = (n \times m)^2$
• 每个状态处理：遍历4个方向，时间为 $O(1)$
• 单次查询时间：$O((n \times m)^2)$
• 总时间复杂度：$O(q \times (n \times m)^2)$，其中 $q$ 为查询次数

对于 $n, m \leq 30$ 且 $q \leq 500$ 的数据范围，该算法在优化编译（O2）下可通过所有测试点。

总结

本解法通过BFS遍历所有可能的状态，保证找到最短移动路径。核心是合理表示状态并正确处理状态转移，通过访问标记避免重复处理相同状态，提高效率。