题解 CF2034C

· · 题解

题意：

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

思路：

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

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

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

模拟即可。

程序如下：

#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