Post List
孙悟空救师傅
# [牛客网 235903] 孙悟空救师傅 题解
# 📋 题目概述
孙悟空需要在一个 n×n 的网格迷宫中救出师傅。网格中包含不同的房间类型:
字符
含义
备注
K
孙悟空起点
保证有且仅有一个
T
师傅终点
保证有且仅有一个
S
有蛇的房间
最多 5 个,需额外时间
#
墙
不可通过
.
空房间
正常通过
1-m
钥匙
必须按顺序收集
# 🎯 核心约束
移动耗时:
普通移动:1 分钟 / 格
遇到蛇房间:首次进入需额外 1 分钟(共 2 分钟)
打倒蛇后,该房间变为普通房间
钥匙收集顺序:
必须按 1→2→...→m 的顺序收集
收集第 i 种钥匙前,必须已收集前...
more...
算法基础:最小生成树的“两大神功” (Prim & Kruskal)
什么是最小生成树 (MST)?
想象你要给好几个村庄通电,村庄之间连电线的费用不同。你的目标是:用最少的总费用把所有村庄连通,且不形成回路。这个 “最省钱的连接方案” 就是最小生成树。
# 1. Kruskal 算法:加边法 (贪心 + 并查集)
Kruskal 的思想非常直观:总是找最短的那条边。
# 核心步骤:
把图中所有的边按权值(长度)从小到大排序。
依次取出边,如果这条边的两个端点还没连通,就选它;如果已经连通了,就丢弃(防止形成环)。
直到选够了 n−1n-1n−1 条边。
# C++...
more...




