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...

