# G-险恶逃生II

G-险恶逃生II

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
``````

``````#include <iostream>
#define MAX 1000
using namespace std;
char map1[MAX+1][MAX+1];
int hang,lie;
class point1
{
public:
void set_value(int X,int Y)
{
x=X;
y=Y;
}
point1 operator+(point1 c)
{
point1 e;
e.set_value(x+c.x,y+c.y);
return e;
}
int x;
int y;
};
struct queue1
{
point1 a;
int th;
queue1 *rear;
}*top1,*now1;
bool check1(point1 will,bool used[][MAX+1])
{
if(will.x<0||will.x>=hang||will.y<0||will.y>=lie)return false;
if(used[will.x][will.y])return false;
if(map1[will.x][will.y]=='T')return false;
return true;
}
void push1(point1 a,int t)
{
now1->rear=new queue1;
now1->a=a;
now1->th=t;
now1=now1->rear;
}
void pop1(point1 &a,int &TH)
{
a=top1->a;
TH=top1->th;
queue1 *temp=top1;
top1=top1->rear;
delete temp;
}
int main()
{
while(cin>>hang>>lie)
{
bool used[MAX+1][MAX+1]={0};
top1=now1=new queue1;
int i,j;
point1 exsit;
for(i=0;i<hang;i++)
{
for(j=0;j<lie;j++)
{
cin>>map1[i][j];
if(map1[i][j]=='E')
{
exsit.set_value(i,j);
}
}
map1[i][lie]='\0';
}
int sum=0;
int exe;
int TH=0;
bool findOut=false;
used[exsit.x][exsit.y]=true;
point1 present;
now1->a=exsit;
now1->th=0;
now1->rear=new queue1;
now1=now1->rear;
pop1(present,TH);
while(1)
{
for(i=0;i<4;i++)
{
if(!check1(will,used))continue;
used[will.x][will.y]=true;
push1(will,TH+1);
}
if(top1==now1)break;
pop1(present,TH);
if(findOut)
{
if(TH>exe)break;
}
if(map1[present.x][present.y]!='S')
{
sum+=map1[present.x][present.y]-'0';
}
else
{
findOut=true;
exe=TH;
}
}
cout<<sum<<endl;
}
return 0;
}
/*
5 5
S9999
TTTT9
99999
9TTTT
9999E
*/``````

``````#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
int m,n;
char a;
int  l;
typedef struct{
int x,y;
int foot;
}stu;
int dx={1,-1,0,0};
int dy={0,0,1,-1};
queue<stu>q;
int sum=0;//×ÜµÄ»µµ°ÊýÄ¿
int maxi=99999999;//×î´ó²½Êý
int bfs(stu now)
{
for(int i=0;i<4;i++)
{
int tx=now.x+dx[i];
int ty=now.y+dy[i];
if(tx>=0&&tx<m&&ty>=0&&ty<n)//ÔÚ·¶Î§ÄÚ
if(a[tx][ty]!='T'&&l[tx][ty]==0)
{
l[tx][ty]=1;
if(a[tx][ty]>='0'&&a[tx][ty]<='9')//
{
stu temp;
temp.x=tx;
temp.y=ty;
temp.foot=now.foot+1;//×ÜµÄ²½Êý
if(temp.foot>maxi)
{
return 1;
}
sum+=a[tx][ty]-'0';
q.push(temp);
}
else if(a[tx][ty]=='S')
{
stu temp;
temp.x=tx;
temp.y=ty;
temp.foot=now.foot+1;//×ÜµÄ²½Êý
maxi=temp.foot;
q.push(temp);
}
}
}
return 0;//±íÊ¾Õý³£
}
int dfs()
{
sum=0;//×ÜµÄ»µµ°ÊýÄ¿
maxi=9999999;//×î´ó²½Êý
int x,y;
memset(l,0,sizeof(l));
for(int i=0;i<m;i++)
{
scanf("%s",a[i]);
for(int j=0;j<n;j++)
{
if(a[i][j]=='E')
{
x=i;
y=j;
}
}
}
stu temp;
temp.x=x;
temp.y=y;
temp.foot=0;
l[x][y]=1;
q.push(temp);
while(!q.empty())
{
stu now=q.front();
q.pop();
if(bfs(now))
{
break;
}
}
while(!q.empty())
{
q.pop();
}
printf("%d\n",sum);
}
int main()
{
while(scanf("%d %d",&m,&n)!=EOF)
{
dfs();
}
}``````