1761: 迷宫的最短路径
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:26
解决:7
题目描述
寻找迷宫的最短路径。迷宫的障碍物分三种,一种不可动的墙用A表示,第二种可以挖的墙用B表示,挖的时间与走一格的时间同;第三种要花100元定向爆破的墙用C表示。在迷宫移动一格要10元。在迷宫只能向上下左右的方向移动。
请找出最短的路,并求出花费多少?
输入
输入多组数据,每组数据先输入m,n,表示m行n列的迷宫,接下来输入m*n个数据值为0或A、B、C,0表示可以走通,A表示受阻。迷宫的入口设为0,0,出口设为m-1,n-1。
输出
求出迷宫的最短路径。格式如样例。
样例输入 复制
4 4
0 A B C
B C 0 0
0 0 0 0
A A A C
样例输出 复制
走了7步,花费180