G-险恶逃生II

G-险恶逃生II

时间： 1ms        内存：128M

描述：

    SOS!!!koha is trapped in the dangerous maze.He need your help again.

    The maze is a 2D grid consisting of n rows and m columns. Each cell in the maze may have a stone or may

be occupied by zero or more monsters. The cell that has a stone Koha(including the monsters) cannot enter. Only one of the cells is designated as the exit cell.

    Kona,including the monsters may move in the maze.In a single move,each of them may perform one of the Following actions:

    1. do nothing

    2. move from the current cell to one of the four adjacent cells.

    3. if Koha is located on the exit cell, he may leave the maze. Only he can perform this move — all Monsters will never leave the maze by using this type of movement.

    After each time Kona makes a single move,each of the monsters simultaneously make a single move ,however the choice of which move to make may be different for each of the monsters.

 

    If koha and x(x>0) monsters are located on the same cell, exactly x monsters will ensue that time(since he will be battling each of those x breeders once).After the battle, all of those x monsters will be killed.

    Now,Koha would like to leave the maze,however the monsters will all know his exact sequence of moves even before he makes his first move.All of them will move in such way that will guarentee a monster battle with Koha,if possible. The monsters that couldn't battle him will do nothing.

 

    All right.Your task is to print the mininum number of monster battles that kona must participates in,note that you are not required to minimize the number of moves kona makes.

输入：

For each case,the first line consists of two integes: n and m(1<=n,m<=1000),denoting the number of rows and the number of columns in the maze.the next n rows will echo depict a row of the map,where each character represents the content of a single cell:

'T':A cell occupied by a stone.

'S':An empty cell,and Kona's starting position.

'E':An empty cell,and where the exit is located.

A digit(0-9): A cell represented by a digit x means that the cell is empty and is occupied by x monsters(if x is zero,it means the cell is not occupied by any monsters).

 

It is guaranteed that it will be possible for Kona to leave the maze.

输出：

For each case,ouput a single line denoted the mininum possible number of monster battles that koha has to participate in if you pick a strategy that minimize this number.

示例输入：

5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000
1 4
SE23

示例输出：

3
2

提示：

参考答案：

解锁文章

没有看到答案？微信扫描二维码可免费解锁文章

使用微信扫描二维码打开广告页面后可以立即关闭，再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供，并不代表本站观点！

已经扫描此二维码？点此立即跳转

文章解锁成功，即将自动跳转，点此立即跳转