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