AcWing 3825. 逃离大森林
原题链接
中等
作者:
白墙
,
2021-09-03 15:17:39
,
所有人可见
,
阅读 301
这样的点满足到终点距离小于等于到起点到终点的距离
可以用反证法证明
如果存在到终点距离大于dist[s][e]的点
这样的点最终会先于起点到达终点。但是根据bfs的过程,他到起点的距离大于dist[s][e],所以肯定是在后面才到的,这时候这个人已经离开了。不能再pk了。所以矛盾了。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e3 + 10;
int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];
queue<pair<int,int>> q;
void bfs () {
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
while (q.size()) {
auto t = q.front(); q.pop();
for (int i = 0; i < 4; i ++) {
int nx = t.first + dx[i], ny = t.second + dy[i];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
if (g[nx][ny] == 'T') continue;
if (dist[nx][ny] > dist[t.first][t.second] + 1) {
dist[nx][ny] = dist[t.first][t.second] + 1;
q.push({nx, ny});
st[nx][ny] = true;
}
}
}
}
int main () {
memset (dist, 0x3f, sizeof dist);
cin >> n >> m;
int s, e;
for (int i = 1; i <= n; i ++)
{
cin >> (g[i] + 1);
for (int j =1 ; j <= m; j ++) {
if (g[i][j] == 'E') {
q.push({i, j});
dist[i][j] = 0;
}
if (g[i][j] == 'S') {
s = i, e = j;
}
}
}
bfs();
int ans= 0;
// cout << dist[s][e]<< endl;
for (int i = 1; i <= n; i ++) {
for (int j= 1; j <= m; j ++) {
if (dist[i][j] <= dist[s][e] && g[i][j] > '0' && g[i][j] <= '9') {
ans += (g[i][j] - '0');
// cout << i << " " << j << " " << dist[i][j] << endl;
}
}
}
cout << ans << endl;
return 0;
}