题解：B4214 [常州市赛 2022] 迷宫探险

· · 题解

前置

传送门

AC记录

题意

有一个 n\times n 的地图，在这些地图中，有一些自动计分器，最先到达这个地点的人加一分，如果有多个人同时到达，则都会加上一分。

思路

如果是从这些人开始的话，会很麻烦，我们不妨逆向思维一下，从这些自动计分器出发，再到这些人，就会简单许多。

这时候，就掏出我们的秘密武器，那就是——

BFS！

我们从这些自动计分器出发，用 BFS 找出第一个搜到的人，或者这个人的距离是等于第一个搜到的人，就把分数加一，最后再取最大值和总和就行了。

Code

const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,cnt[105][105],vis[105][105],maxn,sum;
char a[105][105];
struct node{
    int x,y;
};
void bfs(int sx,int sy){
    memset(vis,-1,sizeof vis);
    int minn=-1;
    queue<node>q;
    q.push({sx,sy});
    while(!q.empty()){
        node u=q.front();
        q.pop();
        if(a[u.x][u.y]=='@'){
            if(minn==-1) minn=vis[u.x][u.y];
            if(vis[u.x][u.y]<=minn) cnt[u.x][u.y]++;
            continue;
        }
        for(int i=0;i<4;i++){
            int nx=u.x+dx[i],ny=u.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>n||~vis[nx][ny]||a[nx][ny]=='#') continue;
            vis[nx][ny]=vis[u.x][u.y]+1;
            q.push({nx,ny});
        }
    }
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]=='$')
                bfs(i,j);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            maxn=max(maxn,cnt[i][j]),sum+=cnt[i][j];
    cout<<maxn<<'\n'<<sum<<'\n';
    return;
}