题解 CF2034C

题意：

一个有方向的迷宫，必须按照箭头方向移动，有些箭头未指定。问最多有多少起始格子无法离开迷宫。

思路：

我们无法改变确定了的格子，所以先用一个 dfs 把所有已经确定的格子遍历一遍，确认到了哪些格子一定可以逃离迷宫。

接着，我们考虑未确定的格子。如果有任何周围的格子指向未确定的这个格子，那么它一定是无法离开迷宫的（可以将两个格子互相指向对方）。如果周围有任何未确定的格子，两个格子互相指向对方，也可以做到困在迷宫中。如果周围有任何无法离开迷宫的方格，将它指向这个方格也永远出不去。

对于任何一个未确定的格子，只要它周围的四个格子中有以上任意一种情况，都是可以离开迷宫的。对于任何一个已经确定的格子，只有当它一定指向迷宫之外时才可逃离，否则一定会被困住。

模拟即可。

程序如下：

CPP

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=1e3+5;
int T,n,m;
char mp[N][N];
bool vis[N][N];
struct TER{int x,y;}a[N][N],f[N][N];
TER dfs(int x,int y){
	if(x<1||x>n||y<1||y>m)return a[x][y]={-1,-1};
	if(a[x][y].x==114514)return {114514,114514};
	if(vis[x][y]||mp[x][y]=='?')return a[x][y]={114514,114514};
	if(f[x][y].x==-1||a[x][y].x==-1)return a[x][y]={-1,-1};
	vis[x][y]=true;
	a[x][y]=dfs(f[x][y].x,f[x][y].y);
	vis[x][y]=false;
	return a[x][y];
}
int main(){
	scanf("%d",&T);
	while(T--){
		int ans=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%s",mp[i]+1);
			for(int j=1;j<=m;j++){
				if(mp[i][j]=='U'){
					if(i==1)f[i][j]={-1,-1};
					else f[i][j]={i-1,j};
				}
				if(mp[i][j]=='D'){
					if(i==n)f[i][j]={-1,-1};
					else f[i][j]={i+1,j};
				}
				if(mp[i][j]=='L'){
					if(j==1)f[i][j]={-1,-1};
					else f[i][j]={i,j-1};
				}
				if(mp[i][j]=='R'){
					if(j==m)f[i][j]={-1,-1};
					else f[i][j]={i,j+1};
				}
			}
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				if(mp[i][j]!='?'&&a[i][j].x!=-1&&a[i][j].x!=-114514){
					a[i][j]=dfs(i,j);
				}
			}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				if(mp[i][j]!='?'&&a[i][j].x!=-1)ans++;
				else if(mp[i][j]=='?'){
					if(a[i-1][j].x==114514||a[i+1][j].x==114514||a[i][j-1].x==114514||a[i][j+1].x==114514)ans++;
					else if(mp[i-1][j]=='?'||mp[i+1][j]=='?'||mp[i][j-1]=='?'||mp[i][j+1]=='?')ans++;
				}
			}
		printf("%d\n",ans);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				a[i][j]={0,0},f[i][j]={0,0},vis[i][j]=false,mp[i][j]=0;
	}
	return 0;
}

文章操作

题意：

思路：

程序如下：

THE END

相关推荐

评论

题解 CF2034C