The Forset NC14325

标签：Forset tx ty int NC14325 tp ey ex

link

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;
//如果坏人可以到达终点，并且距离终点的距离小于等于 起点到终点的距离，那么必然会相遇
//所以我们从终点出发找起点，在找到起点之前如果到达坏人所在地方，就更新距离数组d
int d[N][N];
char g[N][N];
int ex,ey,sx,sy;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void bfs(){
    queue<pair<int,int>>q;
    q.push({ex,ey});
    int flag = 0;
    while(q.size()){
        auto tp = q.front();
        q.pop();
        int x = tp.first;
        int y = tp.second;
        for(int i = 0; i < 4; i++){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(g[tx][ty] == 'T' || d[tx][ty] != -1) continue;
            else if(g[tx][ty] == 'S'){
                d[tx][ty] = d[x][y] + 1;
                flag = 1;
            }
            else{
                d[tx][ty] = d[x][y] + 1;
                q.push({tx,ty});
            }
        }
    }
}
int main(){
    int n, m;
    while(cin >> n >> m){
        memset(d,-1,sizeof d);
        fill(g[0],g[0] + N * N, 'T');
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                cin >> g[i][j];
                if(g[i][j] == 'E') ex = i, ey = j;
                else if(g[i][j] == 'S') sx = i, sy = j;
            }
        d[ex][ey] = 0;
        bfs();
        int ans = 0;
        int num = d[sx][sy];
     //   cout << num << endl;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                if(isdigit(g[i][j])){
                    if(d[i][j] <= num && d[i][j] != -1) ans += g[i][j] - '0';
                }
            }
        cout << ans << endl;
    }
}

标签：Forset,tx,ty,int,NC14325,tp,ey,ex
From： https://www.cnblogs.com/index-12/p/17296736.html