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.

/*
ID: zypz4571
LANG: C++
TASK: 192d.cpp
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>

#define INF 0x3f3f3f3f
#define REP(i, n) for(int i=0;i<int(n);++i)
#define FOR(i, a, b) for(int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for(int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for(int i=1;i<=int(n);++i)
#define mid int m=(l+r)/2
using namespace std;
int dir[4][2] = {{0,-1}, {0, 1}, {-1, 0}, {1, 0}};
char mat[1003][1003];
struct Node {
    int x, y, time;
};
Node start, end;
int ans, matime[1003][1003], n, m;
bool vis[1003][1003];
void bfs(Node end) {
    queue<Node> q; q.push(end);
    while (!q.empty()) {
        Node tmp; tmp = q.front(); q.pop();
        REP (i, 4) {
            int x, y;
            x = tmp.x + dir[i][0]; y = tmp.y + dir[i][1];
            if (x>=0 && x<n && y>=0 && y<m && mat[x][y] != 'T' && !vis[x][y]) {
                Node t; t.x = x; t.y = y; t.time = tmp.time + 1; matime[x][y] = t.time;
                q.push(t); vis[x][y] = true;
            }
        }
    }
}
int main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
    cin>>n>>m;
    memset(vis, false, sizeof(vis));
    REP (i, n) {
        cin>>mat[i];
        REP (j, m) {
            if (mat[i][j] == 'E') {
                end.x = i, end.y = j; end.time = 0;
                vis[i][j] = true;
                matime[i][j] = 0;
            } else if (mat[i][j] == 'S') {
                start.x = i, start.y = j;
                matime[i][j] = INF;
            } else matime[i][j] = INF;
        }
    }
    bfs(end);
    int Time = matime[start.x][start.y], ans = 0;
    REP (i, n) {
        REP (j, m) {
            if (isdigit(mat[i][j]) && matime[i][j] != INF) {
                if (Time >= matime[i][j]) ans += (mat[i][j]-'0');
            }
        }
    }
    printf("%d\n", ans);
        return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

standard dfs