算法实验作业
算法实验作业算法实验作业
算法实验作业 6
66
6-
--
-2
2 2
2 骑士救公主问题
骑士救公主问题骑士救公主问题
骑士救公主问题
★
★★
★问题描述
问题描述问题描述
问题描述:
::
:
公主被魔王抓走了，勇敢的骑士需要拯救出美丽的公主。他进入了魔王的城
堡，魔王的城堡是一座很大的迷宫。为了使问题简单化，我们假设这个迷宫是一
个N*M的二维方格。骑士从左上角(0，0)位置进入迷宫，公主在右下角(N-1,M-1)
位置。迷宫里有一些陷阱，骑士不能进入有陷阱的方格。骑士只能移动到相邻（上
下左右四个方向)的方格内，并且一秒只能移动一步，就是说，如果骑士在(x,y）
一步只能移动到(x-1,y),(x+1,y),(x,y-1),(x,y+1)其中的一个位置上。地图由
‘.’，‘#’，n(0≤n≤9)三种符号构成，‘.’表示平地骑士可以进入，‘#’表示
陷阱骑士不能进入，n表示该方格有一个生命力为n的怪物，骑士需要花费n秒时
间才能消灭它。
★
★★
★实验任务
实验任务实验任务
实验任务：
：：
：
给定迷宫的地图，请你计算出骑士救出公主的最短时间，如果不能救出公主
请输出“-1”。
★
★★
★数据输入
数据输入数据输入
数据输入：
：：
：
每组输入数据的第一行为两个整数n和m(1<n≤200，1<m≤200)，表示地图的
大小。接下来有n行每行有m个字符，表示每一个方格中的地形。
★
★★
★结果输出
结果输出结果输出
结果输出:
::
:
对于每组输入数据输出一行一个整数，表示骑士救出公主的最短时间，如果
不能救出公主请输出“-1”。
输入示例
输入示例输入示例
输入示例1
11
1
输出示例
输出示例输出示例
输出示例1
11
1
5 6
.##.1.
..#.2.
2...#.
...##.
#####.
13
输入示例
输入示例输入示例
输入示例2
22
2
输出示例
输出示例输出示例
输出示例2
22
2
5 6
.##...
..##1.
2...#.
...##.
#####.
-1
