打怪救公主 公主被魔王抓起来关在了迷宫的某处，骑士想要拯救公主，也进入了迷宫。 但是魔王不会轻易让骑士拯救公主，魔王在迷宫中安排了许多怪兽。 每个怪兽都有血量，骑士也有初始血量，骑士打败怪兽后血量的减少量为怪物的血量值，血量减到0，骑士会死去。 迷宫由m*n个方块组成，每个方块有墙或者路或者怪物，骑士在其中一个方块上，他每个时间单位可以四个方向(上、下、左、右)走到相邻方格，若遇到怪物，必须打败怪物才能继续前进。 请帮忙判断骑士能否成功拯救公主，如果能，给出骑士还剩的最大血量。 时间限制：1000 内存限制：65536 输入 第一行为三个整数m、n和t，t表示骑士的初始血量。(m,n <= 20, t <= 30) 第2至m+1行描述了迷宫，迷宫以m行n列的方格组成，若方格为"."则表示骑士可以通过，若方格为"#"则表示墙，骑士不能通过，若方格为数字则表示怪物，数字为怪物的血量，保证怪物的血量小于10(一位数)。"*"表示了骑士当前所在的位置，"+"表示公主被囚禁的位置。 输出 若骑士能成功拯救公主，则输出骑士走到公主所囚禁方格所剩最大血量，否则输出0。 样例输入 5 6 10 ..*... .#2### 5#..4# .##9.# .#+..# 样例输出 4
正确答案：参考程序（C++）：BFS最短路带血量约束。骑士初始血量t，遇到数字怪扣血，血量>0。求能到达公主的最大剩余血量。用Dijkstra/BFS按剩余血量最大化扩展，或DP状态[x][y]记录最大剩余血量。样例输出4。核心：带权BFS求最大剩余血量。
试卷来源：202303 青少年等级考试C/C++真题五级