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

Problem

给你一张地图，这个地图上有一些一次性的计分器，最早踩上这个点的玩家会加

1

分，然后该计分器消失。如果有多个玩家同时到达有计分器的格子，那么这些玩家都能得到

1

分。

Solution

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

AC 记录

Code

CPP

#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;
}

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

文章操作

Problem

Solution

Code

相关推荐

评论

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