分析题目与解题方法

题目背景

这是一道典型的迷宫路径搜索问题，结合了钥匙收集和门解锁的机制。地图由字符矩阵表示，包含以下元素：

• S：起点。
• X：障碍物。
• .：可通行的空地。
• a-e：小写字母代表钥匙。
• A-E：大写字母代表门。
• G：终点。

目标是从起点找到一条路径到达终点，并在途中收集足够的钥匙来打开所有需要的门。

解题思路

1. 数据结构

• 二维数组 vis[101][101]：记录某位置是否已经访问过。
• 二维数组 vis_door[101][101]：记录某门是否已经被钥匙打开。
• 结构体 key[101]：统计每种钥匙的数量及其当前已收集的数量。
• 队列 <node>：用于广度优先搜索（BFS），存储当前路径中的节点。

2. BFS 实现

• 初始化：
  • 读取地图并初始化相关变量。
  • 确定起点位置，并将其入队。
• 搜索过程：
  • 每次从队列中取出一个节点，尝试向四个方向扩展。
  • 对于每个新位置，根据其字符类型进行不同操作：
    • 如果是障碍物 (X) 或已经访问过，则跳过。
    • 如果是钥匙 (a-e)：
      • 更新对应的钥匙计数。
      • 如果所有钥匙都已收集完毕，检查是否有门需要解锁。
    • 如果是门 (A-E)：
      • 判断是否可以打开门（即钥匙是否齐全）。
      • 如果可以打开，则标记为已访问。
    • 如果是终点 (G)：
      • 设置标志位 flag 为 true，表示找到了路径。
    • 如果是普通空地 (.)，直接入队继续搜索。
• 终止条件：
  • 当队列为空且未找到路径时，输出 "NO"。
  • 如果找到终点，输出 "YES"。

关键点解析

1. 钥匙与门的关系：

   • 小写字母代表钥匙，大写字母代表门。
   • 门的解锁条件是对应的小写字母钥匙数量达到要求。
   • 例如，门 A 需要钥匙 a 的数量满足 k['a'-'A'].cnt >= k['a'-'A'].tot。

2. 状态压缩：

   • 使用 vis 和 vis_door 分别管理普通位置和门的状态，避免重复计算。

3. BFS 的高效性：

   • BFS 是解决最短路径问题的经典算法，适用于此类迷宫问题。

代码实现分析

以下是代码的主要部分及其功能：

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

using namespace std;

int n, m;
int vis[101][101], vis_door[101][101];
char map[101][101];

// 方向向量 (上下左右)
int x[5] = {1, -1, 0, 0};
int y[5] = {0, 0, 1, -1};

struct node {
    int x, y;
};

struct key {
    int tot, cnt;
} k[101];

int main() {
    while (~scanf("%d%d", &n, &m) && (n || m)) {
        // 初始化
        bool flag = 0, a;
        memset(k, 0, sizeof(k));
        memset(vis, 0, sizeof(vis));
        memset(vis_door, 0, sizeof(vis_door));

        // 输入地图
        for (int i = 1; i <= n; i++)
            scanf("%s", map[i] + 1);

        // 定义队列
        queue<node> q;
        node st, t, p;

        // 找到起点位置
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (map[i][j] == 'S')
                    st.x = i, st.y = j;
                else if (map[i][j] == 'X')
                    vis[i][j] = 1;
                else if (map[i][j] >= 'a' && map[i][j] <= 'e')
                    k[map[i][j] - 'a'].tot++;

        // 起点入队
        q.push(st);

        // BFS 搜索
        while (!q.empty()) {
            p = q.front();
            q.pop();

            // 四个方向扩展
            for (int i = 0; i <= 3; i++) {
                int nx = p.x + x[i];
                int ny = p.y + y[i];

                // 边界检查
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                    if (!vis[nx][ny]) {
                        if (map[nx][ny] >= 'a                            if (++k[map[nx][ny] - 'a'].cnt == k[map[nx][ny] - 'a'].tot) {
                                // 如果钥匙收集完毕，尝试解锁门
                                for (int ii = 1; ii <= n; ii++)
                                    for (int jj = 1; jj <= m; jj++)
                                        if (map[ii][jj] == map[nx][ny] + ('A' - 'a')) {
                                            node hh;
                                            hh.x = ii;
                                            hh.y = jj;
                                            if (vis_door[ii][jj]) {
                                                q.push(hh);
                                                vis[ii][jj] = 1;
                                            }
                                        }
                            }
                        } else if (map[nx][ny] == 'G') {
                            // 找到终点
                            flag = 1;
                            break;
                        } else if (map[nx][ny] >= 'A' && map[nx][ny] <= 'E') {
                            // 遇到门
                            if (k[map[nx][ny] - 'A'].tot == k[map[nx][ny] - 'A'].cnt &&
                                k[map[nx][ny] - 'A'].cnt >= 1) {
                                t.x = nx;
                                t.y = ny;
                                q.push(t);
                                vis[nx][ny] = 1;
                            } else {
                                vis_door[nx][ny] = 1;
                            }
                        } else if (map[nx][ny] == '.') {
                            // 可通行空地
                            t.x = nx;
                            t.y = ny;
                            q.push(t);
                            vis[nx][ny] = 1;
                        }
                    }
                }
            }

            // 如果找到终点，退出循环
            if (flag)
                break;
        }

        // 输出结果
        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}