codeforces 192 D

link: http://codeforces.com/contest/330/problem/D
The discription looks so long, but the problem is simple if you can grasp the problem quickly.
 1 /*
 2 ID: zypz4571
 3 LANG: C++
 4 TASK: 192d.cpp
 5  */
 6 
 7 #include <iostream>
 8 #include <cstdio>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <cmath>
12 #include <cctype>
13 #include <algorithm>
14 #include <queue>
15 #include <deque>
16 #include <queue>
17 #include <list>
18 #include <map>
19 #include <set>
20 #include <vector>
21 #include <utility>
22 #include <functional>
23 #include <fstream>
24 #include <iomanip>
25 #include <sstream>
26 #include <numeric>
27 #include <cassert>
28 #include <ctime>
29 
30 #define INF 0x3f3f3f3f
31 #define REP(i, n) for(int i=0;i<int(n);++i)
32 #define FOR(i, a, b) for(int i=int(a);i<int(b);++i)
33 #define DWN(i, b, a) for(int i=int(b-1);i>=int(a);--i)
34 #define REP_1(i, n) for(int i=1;i<=int(n);++i)
35 #define mid int m=(l+r)/2
36 using namespace std;
37 int dir[4][2] = {{0,-1}, {0, 1}, {-1, 0}, {1, 0}};
38 char mat[1003][1003];
39 struct Node {
40     int x, y, time;
41 };
42 Node start, end;
43 int ans, matime[1003][1003], n, m;
44 bool vis[1003][1003];
45 void bfs(Node end) {
46     queue<Node> q; q.push(end);
47     while (!q.empty()) {
48         Node tmp; tmp = q.front(); q.pop();
49         REP (i, 4) {
50             int x, y;
51             x = tmp.x + dir[i][0]; y = tmp.y + dir[i][1];
52             if (x>=0 && x<n && y>=0 && y<m && mat[x][y] != 'T' && !vis[x][y]) {
53                 Node t; t.x = x; t.y = y; t.time = tmp.time + 1; matime[x][y] = t.time;
54                 q.push(t); vis[x][y] = true;
55             }
56         }
57     }
58 }
59 int main ( int argc, char *argv[] )
60 {
61 #ifndef ONLINE_JUDGE
62 freopen("in.txt", "r", stdin);
63 #endif
64     cin>>n>>m;
65     memset(vis, false, sizeof(vis));
66     REP (i, n) {
67         cin>>mat[i];
68         REP (j, m) {
69             if (mat[i][j] == 'E') {
70                 end.x = i, end.y = j; end.time = 0;
71                 vis[i][j] = true;
72                 matime[i][j] = 0;
73             } else if (mat[i][j] == 'S') {
74                 start.x = i, start.y = j;
75                 matime[i][j] = INF;
76             } else matime[i][j] = INF;
77         }
78     }
79     bfs(end);
80     int Time = matime[start.x][start.y], ans = 0;
81     REP (i, n) {
82         REP (j, m) {
83             if (isdigit(mat[i][j]) && matime[i][j] != INF) {
84                 if (Time >= matime[i][j]) ans += (mat[i][j]-'0');
85             }
86         }
87     }
88     printf("%d
", ans);
89         return EXIT_SUCCESS;
90 }                /* ----------  end of function main  ---------- */
standard dfs