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[][] = {{,-}, {, }, {-, }, {, }};
char mat[][];
struct Node {
int x, y, time;
};
Node start, end;
int ans, matime[][], n, m;
bool vis[][];
void bfs(Node end) {
queue<Node> q; q.push(end);
while (!q.empty()) {
Node tmp; tmp = q.front(); q.pop();
REP (i, ) {
int x, y;
x = tmp.x + dir[i][]; y = tmp.y + dir[i][];
if (x>= && x<n && y>= && y<m && mat[x][y] != 'T' && !vis[x][y]) {
Node t; t.x = x; t.y = y; t.time = tmp.time + ; 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 = ;
vis[i][j] = true;
matime[i][j] = ;
} 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 = ;
REP (i, n) {
REP (j, m) {
if (isdigit(mat[i][j]) && matime[i][j] != INF) {
if (Time >= matime[i][j]) ans += (mat[i][j]-'');
}
}
}
printf("%d\n", ans);
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
standard dfs