329B - Biridian Forest - CodeForces Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1024;
const int INF = INT_MAX;
 
char a[N][N];
int dp[N][N];
 
const pair<int, int> dist[4] = {
	{0, 1}, {1, 0}, {0, -1}, {-1, 0}
};
 
void matrix_init(int a, int b) {
	for (int i = 0; i <= a + 1; ++i)
		for (int j = 0; j <= b + 1; ++j)
			if (dp[i][j] != -INF)
				dp[i][j] = INF;
 
	for (int i = 0; i <= b + 1; ++i)
		dp[0][i] = dp[a + 1][i] = -INF;
 
	for (int i = 0; i <= a + 1; ++i)
		dp[i][0] = dp[i][b + 1] = -INF;
}
 
void bfs(pair<int, int> v) {
	dp[v.first][v.second] = 0;
	
	queue<pair<int,int>> q;
	q.push({ v.first, v.second });
	
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
 
		for (int i = 0; i < 4; ++i) {
			int x = cur.first + dist[i].first;
			int y = cur.second + dist[i].second;
			int val = dp[cur.first][cur.second];
 
			if (dp[x][y] > -INF)
				if (dp[x][y] > val + 1) {
					dp[x][y] = val + 1;
					q.push({ x, y });
				}
		}
	}
}
 
signed main() {
	int n, m;
	cin >> n >> m;
 
	pair<int, int> start, exit;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
			if (a[i][j] == 'S')
				start = { i, j };
			
			if (a[i][j] == 'E')
				exit = { i, j };
			
			if (a[i][j] == 'T')
				dp[i][j] = -INF;
		}
	
	matrix_init(n, m);
	bfs(exit);
 
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (dp[i][j] <= dp[start.first][start.second])
				ans += (a[i][j] - '0') * (a[i][j] >= '0' && a[i][j] <= '9');
	
	cout << ans << '\n';
}/*1698131912.8649504*/