这道题要求求出从起点到终点,所遇坏人数量最少是多少,而坏人会移动,所以直接求解显然比较麻烦。
在这里瞪眼观察到一个结论:如果坏人到E的距离,小于或等于S到E的距离,那么该坏人必会遇上;而如果坏人到E的距离,大于S到E的距离,则遇不上。
前半句话很好证明,让该处的坏人直接向E出发,则在终点处必能相遇。
后半句话比较显然(翻译:我想到一个绝妙的证法,但这里的地方不够写...)
以下是AC代码,感觉在计算ans的时候可以优化:
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1005; typedef pair<int, int> PII; int n, m, sx, sy, ex, ey, ans; char g[N][N]; int d[N][N]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, 1, -1}; void bfs() { queue<PII> q; q.push({ex, ey}); d[ex][ey] = 0; bool flag = true; while(q.size()) { auto p = q.front(); q.pop(); for(int i = 0; i < 4; i ++) { int _x = p.first + dx[i], _y = p.second + dy[i]; if(_x == sx && _y == sy) { flag = false; } if(_x >= 1 && _x <= n && _y >= 1 && _y <= m && d[_x][_y] == -1 && g[_x][_y] != 'T') { d[_x][_y] = d[p.first][p.second] + 1; if(flag) { q.push({_x, _y}); } } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin >> n >> m) { memset(d, -1, sizeof d); ans = 0; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { cin >> g[i][j]; if(g[i][j] == 'S') { sx = i, sy = j; } if(g[i][j] == 'E') { ex = i, ey = j; } } } bfs(); int lst = d[sx][sy]; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(g[i][j] >= '1' && g[i][j] <= '9' && d[i][j] != -1 && d[i][j] <= lst) { ans += (int)(g[i][j] - '0'); } } } cout << ans << '\n'; } return 0; }