2021.11.06 / bfs
题目名：逃离大森林
www.acwing.com/problem/content/description/3828/

本体难点在于贪心，要理解从终点开始bfs遍历所有位置的最短路

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
const int dx[] = {1,-1,0,0}, dy[] = {0,0,-1,1};
const int N = 1010;

int n, m, sssp = 2e9;
int breeder[N][N], dist[N][N];
pii boy, END;
queue<pii> q;

bool value(int x, int y){
    return x && y && x <= n && y <= m && ~breeder[x][y] && dist[x][y] == 0;
}

int bfs(){
    int ans = 0;
    q.push(END);
    dist[END.first][END.second] = 1;
    while(q.size()){
        auto now = q.front(); q.pop();
        int x = now.first, y = now.second;
        if(sssp < dist[x][y]) return ans;
        ans += breeder[x][y];

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(!value(nx, ny)) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
            if(make_pair(nx, ny) == boy) sssp = dist[nx][ny];
        }
    }
    return ans;
}


int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            char c; cin >> c;
            if(c == 'T') breeder[i][j] = -1;
            else if(c == 'S') boy = {i,j};
            else if(c == 'E') END = {i, j};
            else breeder[i][j] = c ^ 0x30;
        }

    printf("%d\n",bfs());  

    return 0;
}