由于牛客的渲染问题，你可以进入我的博客查看

[牛客网 235903] 孙悟空救师傅 题解

📋 题目概述

孙悟空需要在一个 n×n 的网格迷宫中救出师傅。网格中包含不同的房间类型：

🎯 核心约束

1. 移动耗时：

   • 普通移动：1分钟/格
   • 遇到蛇房间：首次进入需额外1分钟（共2分钟）
   • 打倒蛇后，该房间变为普通房间

2. 钥匙收集顺序：

   • 必须按 1→2→...→m 的顺序收集
   • 收集第 i 种钥匙前，必须已收集前 i-1 种
   • 每种钥匙至少收集一把

3. 救出条件：

   • 到达 T 位置
   • 已收集所有 m 种钥匙

🧠 算法设计

1. 状态建模

这是典型的 状态空间搜索 问题。由于钥匙收集有顺序要求，且蛇房间状态会改变，我们需要维护多维状态：

状态定义：

state = (x, y, k)
- (x, y): 当前位置坐标
- k: 已收集的钥匙种类数 (0 ≤ k ≤ m)

2. 状态转移图

       普通移动 (+1min)
state ──────────────→ 新位置
   │
   │ 遇到蛇房间 (+2min)
   │ (并标记蛇已被打倒)
   ↓
       收集钥匙 (需 k+1)
state ──────────────→ k增加

3. 算法选择

由于边权有 1 和 2 两种，通常应使用 Dijkstra 或 01-BFS。但本题特殊之处在于：

• 只有首次进入蛇房间是2分钟，之后都是1分钟
• 可以修改地图来记录蛇的状态变化

因此采用 BFS + 状态标记 即可，因为每次扩展时，我们只移动到相邻单元格，且通过标记蛇房间可以保证后续处理正确。

4. 关键处理技巧

(1) 蛇房间的状态处理

// 首次遇到蛇：耗时2分钟，并标记蛇已被打倒
if(g[nx][ny] == -2) {  // -2表示蛇房间
    g[nx][ny] = -1;    // 标记为普通房间
    time_cost = 2;
}

// 后续经过：耗时1分钟（已被标记为-1）
else {
    time_cost = 1;
}

这样处理后，不需要额外的状态位记录蛇的位置，大大简化了状态空间。

(2) 钥匙收集的顺序性保证

int new_key = key;
if(g[nx][ny] == key + 1) {  // 遇到下一种钥匙
    new_key = key + 1;      // 收集
}

只有遇到数字 key+1 时，才更新钥匙状态，确保顺序正确。

5. 搜索实现细节

数据结构

struct State {
    int x, y;      // 位置
    int key;       // 已收集钥匙数
};

int dist[maxn][maxn][10];  // 最短时间记录
// dist[x][y][k]: 到达(x,y)且已收集k种钥匙的最短时间

BFS流程

1. 初始化 dist[起点][0] = 0
2. 将状态(起点, 0)加入队列
3. while 队列非空:
    4. 取出队首状态
    5. 如果是终点且key==m: 返回结果
    6. 向四个方向扩展:
        7. 越界/撞墙: 跳过
        8. 计算新钥匙状态
        9. 计算时间花费(考虑蛇房间)
       10. 如果能更新dist: 入队

6. 复杂度分析

• 状态数: O(n² × m) = 100×100×10 ≈ 10⁵
• 每个状态扩展: 4个方向
• 总操作: ≈ 4×10⁵，完全可行
• 空间复杂度: O(n² × m) ≈ 10⁵ × 4字节 ≈ 400KB

📝 完整代码解析

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int inf = 2e18 + 9;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

struct State {
    int x, y;   // 位置
    int key;    // 已收集钥匙种类数
};

const int maxn = 110;
int g[maxn][maxn];          // 地图
// g[i][j] 含义:
//   -3: 墙('#')
//   -2: 蛇('S')
//   -1: 普通房间('.','K','T')
//   1-m: 钥匙数字

int dist[maxn][maxn][10];   // 最短时间

void solve() {
    int n, m;
    cin >> n >> m;
    
    int start_x, start_y;   // 起点K
    int target_x, target_y; // 终点T
    
    // 1. 读入地图并初始化
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            char c;
            cin >> c;
            
            // 字符转数字表示
            if(c == 'K') {
                start_x = i; start_y = j;
                g[i][j] = -1;
            }
            else if(c == '#') g[i][j] = -3;
            else if(c == '.') g[i][j] = -1;
            else if(c == 'S') g[i][j] = -2;
            else if(c == 'T') {
                target_x = i; target_y = j;
                g[i][j] = -1;
            }
            else g[i][j] = c - '0';  // 钥匙数字
            
            // 初始化距离数组
            for(int k = 0; k <= m; k++) {
                dist[i][j][k] = inf;
            }
        }
    }
    
    // 2. BFS初始化
    queue<State> q;
    q.push({start_x, start_y, 0});
    dist[start_x][start_y][0] = 0;
    
    // 3. BFS搜索
    while(!q.empty()) {
        auto [x, y, key] = q.front();
        q.pop();
        
        // 到达终点且收集完所有钥匙
        if(x == target_x && y == target_y && key == m) {
            cout << dist[x][y][key] << endl;
            return;
        }
        
        // 四个方向扩展
        for(int d = 0; d < 4; d++) {
            int nx = x + dir[d][0];
            int ny = y + dir[d][1];
            
            // 边界和墙检查
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(g[nx][ny] == -3) continue;
            
            // 计算新的钥匙状态
            int new_key = key;
            if(g[nx][ny] == key + 1) {
                new_key = key + 1;
            }
            
            // 计算时间花费
            int time_cost;
            if(g[nx][ny] == -2) {  // 蛇房间
                time_cost = 2;
                // 蛇被打倒，标记为普通房间
                g[nx][ny] = -1;
            } else {
                time_cost = 1;
            }
            
            // 更新最短时间
            int new_time = dist[x][y][key] + time_cost;
            if(new_time < dist[nx][ny][new_key]) {
                dist[nx][ny][new_key] = new_time;
                q.push({nx, ny, new_key});
            }
        }
    }
    
    // 4. 无法到达终点
    cout << "impossible" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}

🎓 涉及知识点

1. 广度优先搜索(BFS)

• 用于无权图的最短路径
• 本题中结合状态压缩形成 状态BFS

2. 状态压缩

• 将钥匙收集进度作为状态维度
• 避免重复访问相同状态
• 状态表示：(位置, 钥匙进度)

3. 动态规划思想

• dist[x][y][k] 数组记录最短时间
• 状态转移方程：

  dist[nx][ny][new_key] = min(
      dist[nx][ny][new_key],
      dist[x][y][key] + time_cost
  )
  

4. 网格图遍历

• 四方向移动：上下左右
• 边界判断：0 ≤ x,y < n

⚠️ 注意事项与边界情况

1. 特殊情况处理

// 无钥匙的情况
if(m == 0) {
    // 直接找最短路径，不考虑钥匙
}

// 所有钥匙都在起点/终点路径上
// BFS会自动处理

2. 输入保证

• n ≤ 100，m ≤ 9
• K 和 T 各出现一次
• S 最多5个
• 数字1-m至少出现一次

3. 常见错误

• 忘记初始化dist数组：应初始化为无穷大
• 钥匙顺序判断错误：必须是 key+1 才收集
• 蛇房间标记时机：只有在首次访问时才标记
• 终点判断条件：必须同时满足位置和钥匙条件

📊 示例分析

示例1

输入：
3 2
K12
..#
S.T
输出：
6

路径解释：

1. K→1 (1分钟)
2. 1→2 (1分钟，收集钥匙2)
3. 2→S (1分钟)
4. S停留 (额外1分钟，打倒蛇)
5. S→. (1分钟)
6. .→T (1分钟) 总计：6分钟

示例2

输入：
2 1
K#
T1
输出：
impossible

钥匙1不可达，无法救出师傅。

💡 优化思考

1. 进一步状态压缩

如果题目要求更严格（如蛇房间较多），可用二进制状态记录：

struct State {
    int x, y;
    int key_state;  // 钥匙状态
    int snake_state;// 蛇状态（二进制位）
};

2. 双向BFS

可从起点和终点同时搜索，在中间状态相遇，能显著减少搜索空间。

3. A*启发式搜索

使用曼哈顿距离作为启发函数，可加速搜索过程。

🏆 总结

本题是一道 状态BFS 的经典题目，关键在于：

1. 将钥匙收集进度作为状态维度
2. 巧妙处理蛇房间（首次访问特殊处理）
3. 使用三维数组记录最短时间
4. 严格保证钥匙收集顺序

通过 BFS + 状态标记 的方法，可以在合理时间内求解，是图论与状态压缩结合的典型应用。