逃离大森林

思路

BFS出从起点到其他不为T的点的距离，累加上距离小于player到终点距离的点上的饲养员数量

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
string g[N];
int d[N][N];
bool st[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int main()
{
    int r, c;
    cin >> r >> c;
    pair<int,int> p, e;
    for (int i = 0 ; i < r ; i ++ ) {
        cin >> g[i];
        for (int j = 0 ; g[i][j] ; j ++ ) {
            if (g[i][j] == 'S') p = {i, j};
            if (g[i][j] == 'E') e = {i, j};
        }
    }
    memset(d, 0x3f,sizeof d);
    d[e.first][e.second] = 0;
    queue<pair<int,int>> q;
    q.push(e);
    st[e.first][e.second] = true;
    while (q.size()) {
        int l = q.size();
        for (int i = 0 ; i < l ; i ++ ) {
            auto t = q.front();
            q.pop();
            for (int j = 0 ; j < 4 ; j ++ ) {
                int x = t.first + dx[j];
                int y = t.second + dy[j];
                if (x >= 0 && x < r && y >= 0 && y < c && !st[x][y] && g[x][y] != 'T') {
                    d[x][y] = min(d[x][y], d[t.first][t.second] + 1);
                    q.push({x, y});
                    st[x][y] = true;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0 ; i < r ; i ++ ) {
        for (int j = 0 ; j < c ; j ++ ) {
            if (g[i][j] >= '0' && g[i][j] <= '9') {
                if (d[i][j] <= d[p.first][p.second]) ans += g[i][j] - '0';   
            }
        }
    }
    cout << ans << endl;
    return 0;
}