题目链接
Codesforces 329B Biridian Forest
思路分析
首先题目中让饲养员根据你自己的行动而行动，较为复杂，考虑简化。我们发现无论自己怎么走，最后一步且为必经之路就是出口。所以我们可以让饲养员全部堆到出口守着你。
所以，我们先用 bfs 跑一个以出口为起点的单源最短路，统计能在你到达出口前到达出口（包括同时）的饲养员数量即可。代码如下，时间复杂度 \(O(n^2)\)。
代码呈现
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;const int N=1010;
int r,c,sx,sy,ex,ey;
int a[N][N],dis[N][N],dx[]={1,-1,0,0},dy[]={0,0,1,-1};void bfs(int sx,int sy){ // 单源最短路queue<pii> q;memset(dis,0x3f,sizeof dis);q.push({sx,sy}),dis[sx][sy]=0;while (!q.empty()){pii u=q.front();q.pop();for (int i=0;i<4;++i){int nx=u.first+dx[i],ny=u.second+dy[i],ns=dis[u.first][u.second]+1;if (nx>0 && nx<=r && ny>0 && ny<=c && a[nx][ny]!=-1 && dis[nx][ny]>ns)dis[nx][ny]=ns,q.push({nx,ny});}}
}
int main(){scanf("%d%d",&r,&c);for (int i=1;i<=r;++i){for (int j=1;j<=c;++j){char ch;scanf(" %c",&ch);if (ch=='T') a[i][j]=-1;else if (ch=='S') sx=i,sy=j;else if (ch=='E') ex=i,ey=j;else a[i][j]=ch-'0';}}bfs(ex,ey);int ans=0;for (int i=1;i<=r;++i){ // 统计for (int j=1;j<=c;++j){if (dis[i][j]<=dis[sx][sy] && (i!=sx || j!=sy)) ans+=a[i][j];}}printf("%d",ans);return 0;
}