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

Cookie_King · 2025-08-26 23:37:57 · 题解

Problem

给你一张地图，这个地图上有一些一次性的计分器，最早踩上这个点的玩家会加 1 分，然后该计分器消失。如果有多个玩家同时到达有计分器的格子，那么这些玩家都能得到 1 分。

Solution

从玩家来 BFS 并不是特别好写，所以我们反过来，从每个计分点开始搜，如果搜到第一个玩家，或者该玩家与第一个到达的玩家距离起点位置相同，那么就把当前玩家的分数加一（因为他们可以同时到达该计分点），最后取最大值和总和就行。

AC 记录

Code

#include<iostream>
//#include<cstdio>
#include<queue>
#define Pii pair<int,int>
#define mp make_pair
using namespace std;
int n,f[105][105],cnt[105][105],mx=0,ans=0;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char a[105][105];
queue<Pii> qe;
void init(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            f[i][j]=-1;
    }
}
void bfs(int sx,int sy){
    int mn=-1;
    f[sx][sy]=0;
    qe.push(mp(sx,sy));
    while(!qe.empty()){
        int x=qe.front().first,y=qe.front().second;
        qe.pop();
        if(a[x][y]=='@'){
            if(mn==-1)//如果这是搜到的第一个玩家
                mn=f[x][y],cnt[x][y]++;
            else if(f[x][y]<=mn)//如果这个玩家和第一个玩家可以同时到达该计分器
                cnt[x][y]++;
            continue;//搜到玩家就不能再拓展了，因为后面一定没法和这个玩家同时到了
        }
        for(int i=0;i<4;++i){
            int nx=x+dir[i][0],ny=y+dir[i][1];
            if(nx<1||nx>n||ny<1||ny>n||f[nx][ny]>=0||a[nx][ny]=='#')
                continue;
            f[nx][ny]=f[x][y]+1;
            qe.push(mp(nx,ny));
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cin>>a[i][j];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(a[i][j]=='$'){
                init();
                bfs(i,j);
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            mx=max(mx,cnt[i][j]),ans+=cnt[i][j];
    }
    printf("%d\n%d\n",mx,ans);
    return 0;
}