1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn = 1000+5;
char w[maxn][maxn];
bool vis[maxn][maxn];
int d[maxn][maxn];
struct ss{
int x, y;
}q[maxn * 1000];
int sx, sy, tx, ty ,ans, n, m;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool judge(int x,int y){
if(x > 0 && y > 0 && x <= n && y <= m &&!vis[x][y])
return true;
return false;
}
int bfs(){
int head=0,tail =1;
vis[tx][ty] = true;
q[0].x = tx;
q[0].y = ty;
d[tx][ty] = 0;
while(head<tail){
ss p = q[head++];
int step = d[p.x][p.y] + 1;
for(int i = 0; i < 4; ++i){
int x = p.x + dx[i];
int y = p.y + dy[i];
if(judge(x, y)){
q[tail].x = x;
q[tail++].y = y;
vis[x][y] = true;
d[x][y] = step;
}
}
}
return 0;
}
int main(){
memset(vis,false,sizeof(vis));
memset(d,127,sizeof(d));
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j){
scanf(" %c", &w[i][j]);
if(w[i][j] == 'E')
tx = i, ty = j;
if(w[i][j] == 'S')
sx = i, sy = j;
if(w[i][j] == 'T')
vis[i][j] = true;
}ans =0;
bfs();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(d[i][j] <= d[sx][sy] && w[i][j] >='0' && w[i][j] <= '9')
ans += w[i][j]- '0';
printf("%d\n",ans);
return 0;
}
|