图综合项目

图 Project 的核心任务是把迷宫场景转化为图问题，再调用 Baseline 中已经实现的算法接口完成求解。Baseline 是算法工具箱，Project 是实际建模和工程使用能力的考查。

Project 考查什么

Project 不只考查会不会写某个算法，更考查能否完成以下转换：

1. 从迷宫文本中识别可通行位置、起点、终点和特殊位置。
2. 把位置或必要状态抽象为顶点。
3. 根据移动规则建立边。
4. 判断边是否需要方向和权重。
5. 选择 BFS、Dijkstra 或其他 Baseline 接口。
6. 将算法输出还原成路径、步数、总代价或判定结果。

从迷宫到图

普通迷宫最短步数可以这样建图：

• 顶点：每个可通行格子。
• 边：上下左右相邻且可走的两个格子之间连边。
• 权重：每一步代价相同，因此使用无权最短路径。

如果迷宫中存在不同地形代价：

• 顶点仍然是可通行格子或状态。
• 边权表示从一个格子移动到另一个格子的代价。
• 算法选择 Dijkstra。

如果存在会改变通行规则的钥匙、门、机关或状态变化，仅用格子坐标可能不够。此时可以把状态也放进顶点，例如 (row, col, has_key)。同一个格子在不同状态下是不同顶点，因为它们之后能走的边可能不同。

当前固定迷宫中的 K 不改变 D 的通行规则：K 只是任务 3 和任务 4 的必经点，D 始终可通过，在带权任务中进入代价为 8。

固定迷宫规则

#####################
#S#.....#...........#
#.#.###.#.####.####.#
#.#.#.#...#.......#.#
#.#.#.#####.#######.#
#.#.....#...#.....#.#
#.##..###.###.###.#.#
#.#...#1112.....#.#.#
#.#.###.###.#.#####.#
#..1#..D#.#.#...#...#
###.#.###...#####.###
#..9#.#.#K......#.#.#
#2###.#.#.#####.#.#.#
#...4.#.......#....E#
#####################

字符含义：

字符	含义
#	墙，不能通过
.	普通道路，进入代价为 1
1-9	数字地形，进入代价等于数字
S	起点
K	钥匙点，任务 3 和任务 4 要求先经过该点
D	危险门，进入代价为 8，不需要 K 解锁
E	终点

建模步骤

1. 读取迷宫尺寸和字符矩阵。
2. 扫描每个格子，记录起点、终点、墙和特殊格子。
3. 为每个可通行位置或状态分配顶点编号。
4. 枚举每个顶点的四个方向，判断移动是否合法。
5. 根据移动代价添加无权边或带权边。
6. 调用 Baseline 中合适的算法接口。
7. 根据 dist[]、prev[] 或生成树边集解释结果。

示例：等代价迷宫

若每次移动都消耗 1 步，可以把每个可通行格子当作顶点，并用无权最短路径求起点到终点的最少步数。

S . .
# # .
. . T

一种编号方式：

0 1 2
# # 3
4 5 6

其中 0 是起点，6 是终点。合法边包括 0-1、1-2、2-3、3-6、4-5、5-6。求 0 到 6 的最短距离即可得到最少步数。

示例：带权迷宫

如果普通地面代价为 1，泥地代价为 3，那么边权应该表示移动进入下一个格子的代价。此时不能只比较步数，需要使用 Dijkstra。

S . M
. # .
. . T

建图时要明确权重含义：可以约定“边权等于进入目标格子的代价”。只要约定稳定，并在实现中始终一致，算法输出的总代价就能解释回原始迷宫。

扩展示例：带钥匙状态

如果扩展迷宫中有门，必须拿到钥匙后才能通过，顶点就不能只用 (row, col)。到达同一个格子但是否持有钥匙不同，会导致后续可走的边不同。

可以使用：

(row, col, has_key)

作为状态顶点。拿到钥匙时，从 (r, c, false) 转移到 (r, c, true)；遇到门时，只有 has_key = true 的状态可以通过。

与 Baseline 的接口关系

• 邻接表和邻接矩阵帮助你保存图。
• BFS 和无权最短路径帮助你解决等代价移动。
• Dijkstra 帮助你解决非负权代价移动。
• Prim 和 Kruskal 帮助你理解带权图连接问题，也可以用于“连通设施、最小成本铺设”等扩展任务。

Project 中不要为了迷宫重新写一套重复算法。更合理的做法是：先建图，再调用 Baseline 中已经通过测试的接口。

提交前自查

• 是否能说明每个顶点代表什么。
• 是否能说明每条边代表什么。
• 是否处理了墙、边界、入口、出口等特殊位置。
• 是否选择了与边权匹配的算法。
• 是否复用了 Baseline 接口，而不是在 Project 中重新写一套重复算法。
• 是否能解释最终路径或总代价。
• 是否能通过多个不同形态的迷宫样例，而不是只通过公开样例。

评分关注点

评分时会同时关注算法结果和建模过程：

• 输入解析是否稳定。
• 图构造是否完整且没有误连边。
• 顶点编号和原始迷宫坐标是否能互相转换。
• 算法选择是否符合边权设置。
• 输出是否能清楚表达路径、步数或总代价。
• 代码是否复用 Baseline 工具箱中的接口。

运行与作业指导

本页对应 src/Graph/Project/。完成迷宫建图和接口调用后，进入 Project 目录运行 make 与 ./graph_project。

完整的 Baseline、Project、输入输出规范和报告要求见：运行与作业指导。