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

前置

题意

有一个

n\times n

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

思路

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

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

BFS！

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

Code

CPP

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

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

文章操作

前置

题意

思路

Code

相关推荐

评论

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