你的朋友Jefferson在一个二维迷宫（可以视为是有N*M个格子的方阵）中迷了路，他目前只知道他的起始坐标（startX, startY）和他需要抵达的目的地坐标（destX, destY）。然而迷宫中有许多格子是不能进入的，还有一些格子是收费的——要知道Jefferson手头的现金（cash）极其有限。所以现在你需要写一个程序来帮助他：给出一条步数最短的路径，让Jefferson能够用手头的现金抵达目的地。

1.　　迷宫表示，迷宫用一个二维矩阵表示。当用户输入N,M后，计算机随机生成一个N*M的迷宫，并显示出来。注意迷宫全封闭，在其边界必须为*，一个合法的迷宫输入可以是：

******

*0500*

*1120*

*0000*

******

其中，第i行j列如果是：

0： 代表空格子

*： 代表不能进入的格子

k(1<=k<=9)：代表进入该格子将一次性收取费用k

2.　　用户可以输入起始坐标起始坐标（startX, startY）和他需要抵达的目的地坐标（destX, destY），以及手中的Cash

3.　　输出详细路径，步数，以及此步数下的花费，示例如下：

(2,2)-(2,3)-(2,4) step:2 cost:5

4.　　注意：

（1）　　最短的路径有可能有多条；

（2）　　也可能不能找到利用手头的现金完成旅行的答案-Your friend Jefferson in a two-dimensional maze (which can be seen as a N* M a grid of squares) in lost



Way, he now knew his starting coordinates (startX, startY) and he needs to reach the destination coordinates (



destX, destY). However, there are many lattice maze is inaccessible, and some for a fee lattice



- To know Jefferson cash on hand (cash) is extremely limited. So now you need to write a program



To help him: a step given the number of shortest path, so that Jefferson could use the cash on hand at destination



.

1. Maze that maze with a two-dimensional matrix. When the user input N, M, the computer



An N* M randomly generated maze, and displayed. Note that the whole maze closed its borders must be*



A legal labyrinth input can be:

******

0500**

* 1120*

* 0000*

******

Among them, first column i row j if:

0: on behalf of sub-space

*: Representatives can not enter the lattice

k (1 <= k <= 9): representative of the grid will be a one-time charge k