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

# 📋 题目概述

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

字符	含义	备注
`K`	孙悟空起点	保证有且仅有一个
`T`	师傅终点	保证有且仅有一个
`S`	有蛇的房间	最多 5 个，需额外时间
`#`	墙	不可通过
`.`	空房间	正常通过
`1-m`	钥匙	必须按顺序收集

# 🎯 核心约束

移动耗时：
- 普通移动：1 分钟 / 格
- 遇到蛇房间：首次进入需额外 1 分钟（共 2 分钟）
- 打倒蛇后，该房间变为普通房间
钥匙收集顺序：
- 必须按 1→2→...→m 的顺序收集
- 收集第 i 种钥匙前，必须已收集前 i-1 种
- 每种钥匙至少收集一把
救出条件：
- 到达 T 位置
- 已收集所有 m 种钥匙

# 🧠 算法设计

# 1. 状态建模

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

状态定义：

1
2
3

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. 输入保证

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

# 2. 常见错误

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

# 📊 示例分析

# 示例 1

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

路径解释：

K→1 (1 分钟)
1→2 (1 分钟，收集钥匙 2)
2→S (1 分钟)
S 停留 (额外 1 分钟，打倒蛇)
S→. (1 分钟)
.→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 的经典题目，关键在于：

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

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

C++ 分层图状态压缩

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