Portal 题解

andychen_2012 · 2022-11-24 10:19:28 · 题解

【DMOI 官方题解】

解题思路

部分分

额，出题人想着第一档部分分应该是乱做吧？暴力 dfs 就行了。而第二档部分分，也就是 60\% 的，应该就是 dfs 加上一些剪枝，或者 01bfs 没有实现好的同学吧。

正解

我们要求的是传送门枪最少使用次数，因此我们不用管走路。所以我们可以将每个连通的空地视为一个连通块。

那么我们就是要看如果要从起点所在的连通块走到终点所在的连通块至少要经过多少连通块。

我们可以发现，如果我们想要从一个连通块抵达另一个连通块，这两个连通块之间必须存在一个地方仅存在一个墙壁,如 ..#.. 左右两个连通块可互相抵达，但 ..##.. 左右两个连通块就不可互相抵达。

不过我们要思考下面这么一个情况：

.***.
*.#..
****#
*..#.
****.

我们用数字表示不同的连通块，一个连通块的空地用同一个数字表示。

1***2
*3#22
****#
*44#5
****5

但我们别忘了地图外面也都是墙，因此我们的真正的地图如下：

#######
#1***2#
#*3#22#
#****##
#*44#5#
#****5#
#######

我们可以发现有如下连通块到达关系，其中 i \to j 表示连通块 i 可以到达连通块 j：

1 -> 2
2 -> 1
2 -> 3
2 -> 4
2 -> 5
4 -> 2
4 -> 3
5 -> 2
5 -> 4

我们发现连通块 2 和 3 之间存在一个地方只有一个墙间隔，但是 3 不能到 2 ， 2 可以到 3 ，因为 3 旁边除了一堵墙以外都是虚空，无法建立两个不同颜色的传送门，但 2 可以。

还是上面那个例子，注意连通块 4 可以抵达连通块 2 和 3，因为传送门是可以穿过虚空的，但是 4 不可以抵达连通块 5，因为不能在虚空中走路。

还要注意，不能在一堵墙上建两面传送门。

想清楚了以上情况后，我们就有一个清晰的思路，可以建立出来一个有向图，i \to j 表示连通块 i 可以抵达连通块 j，每条边的边权都为 1，要求的就是起点所在连通块到终点所在连通块的最短距离，就如上图，我们选择 1 \to 2,2 \to 5 两条边即可到达终点所在连通块。

当然，你也可以采用 01bfs 的方式，不建图跑，但这样的话可能需要进行一定的剪枝，不过如果实现得比较好的话，不剪枝也可以过。

不过代码实现上要考虑到的还是挺多的。

解题代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
inline int read(){
    int x=0;
    int ch=getchar(),f=0;
    while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
    while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return f?-x:x;
}
inline void write(int x,char end='\n'){
    if(x==0){
        putchar('0');
        putchar(end);
        return;
    }
    if(x<0) putchar('-'),x=-x;
    int st[70],sr=0;
    while(x){
        st[sr++]=x%10;
        x/=10;
    }
    while(sr--) putchar(st[sr]+48);
    putchar(end);
    return;
}
const int N=2005,INF=2e9;
const int M=2500005,M2=5000005;
const int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
int n;
char s[N][N];
int dis[N];
int col[N][N];
int head,tail;
struct node{
    int x,y;
};
struct edge{
    int to,nxt;
}e[M2];
int hd[M2],ecnt;
inline void add(int u,int v){
    e[++ecnt].to=v;
    e[ecnt].nxt=hd[u];
    hd[u]=ecnt;
}
node q[M2];
int cango[10],only[M2][2];
#define mp make_pair
map<pair<int,int>,bool> mps;
inline void bfs(){
    int cnt=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(s[i][j]=='.'&&!col[i][j]){
                head=1,tail=0;
                ++cnt;
                q[++tail]=(node{i,j});
                while(head<=tail){
                    node h=q[head++];
                    int x=h.x,y=h.y;
                    col[x][y]=cnt;
                    for(int i=0;i<4;++i){
                        int tx=x+dx[i],ty=y+dy[i];
                        if(s[tx][ty]!='.') continue;
                        if(!col[tx][ty]){
                            col[tx][ty]=cnt;
                            q[++tail]=(node{tx,ty});
                        }
                    }
                }
            }
        }
    }
    for(int i=1;i<=cnt;++i) only[i][0]=only[i][1]=-1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(col[i][j]){
                int g=col[i][j];
                if(s[i-1][j]=='#'){
                    if(only[g][0]==-1){
                        only[g][0]=i-1;
                        only[g][1]=j;
                    }
                    else
                        only[g][0]=only[g][1]=-2;
                }
                if(s[i+1][j]=='#'){
                    if(only[g][0]==-1){
                        only[g][0]=i+1;
                        only[g][1]=j;
                    }
                    else
                        only[g][0]=only[g][1]=-2;
                }
                if(s[i][j-1]=='#'){
                    if(only[g][0]==-1){
                        only[g][0]=i;
                        only[g][1]=j-1;
                    }
                    else
                        only[g][0]=only[g][1]=-2;
                }
                if(s[i][j+1]=='#'){
                    if(only[g][0]==-1){
                        only[g][0]=i;
                        only[g][1]=j+1;
                    }
                    else
                        only[g][0]=only[g][1]=-2;
                }
            }
        }
    }
    for(int i=0;i<=n+1;++i){
        for(int j=0;j<=n+1;++j){
            if(s[i][j]=='#'){
//              printf("now judging:%d %d\n",i,j);
                for(int k=1;k<=4;++k) cango[k]=-1;
                bool nowflag=0;
                if(i<n&&col[i+1][j]) cango[1]=col[i+1][j],nowflag=1;
                if(i>1&&col[i-1][j]) cango[2]=col[i-1][j],nowflag=1;
                if(j<n&&col[i][j+1]) cango[3]=col[i][j+1],nowflag=1;
                if(j>1&&col[i][j-1]) cango[4]=col[i][j-1],nowflag=1;
                if(!nowflag) continue;
                for(int k=j-1;k>=1&&s[i][k]!='#';--k){
                    int c=col[i][k];
                    if(c){
                        for(int l=1;l<=4;++l){
                            if(cango[l]==-1) continue;
                            if(c==cango[l]) continue;
                            if(mps[mp(c,cango[l])]&&mps[mp(cango[l],c)]) continue;
                            if(only[c][0]==-1) continue;
                            if(k==j-1){
                                if(only[cango[l]][0]==-2){
                                    if(!mps[mp(cango[l],c)]){
                                        mps[mp(cango[l],c)]=1;
                                        add(cango[l],c);
//                                      printf("%d %d\n",cango[l],c);
                                    }
                                }
                                continue;
                            }
                            if(only[c][0]==i&&only[c][1]==j) continue;
                            if(mps[mp(c,cango[l])]) continue;
                            mps[mp(c,cango[l])]=1;
                            add(c,cango[l]);
//                          printf("%d %d\n",c,cango[l]);
                        }
                    }
                }
                for(int k=j+1;k<=n&&s[i][k]!='#';++k){
                    int c=col[i][k];
                    if(c){
                        for(int l=1;l<=4;++l){
                            if(cango[l]==-1) continue;
                            if(c==cango[l]) continue;
                            if(mps[mp(c,cango[l])]&&mps[mp(cango[l],c)]) continue;
                            if(only[c][0]==-1) continue;
                            if(k==j+1){
                                if(only[cango[l]][0]==-2){
                                    if(!mps[mp(cango[l],c)]){
                                        mps[mp(cango[l],c)]=1;
                                        add(cango[l],c);
//                                      printf("%d %d\n",cango[l],c);
                                    }
                                }
                                continue;
                            }
                            if(only[c][0]==i&&only[c][1]==j) continue;
                            if(mps[mp(c,cango[l])]) continue;
                            mps[mp(c,cango[l])]=1;
                            add(c,cango[l]);
//                          printf("%d %d\n",c,cango[l]);
                        }
                    }
                }
                for(int k=i-1;k>=1&&s[k][j]!='#';--k){
                    int c=col[k][j];
                    if(c){
                        for(int l=1;l<=4;++l){
                            if(cango[l]==-1) continue;
                            if(c==cango[l]) continue;
                            if(mps[mp(c,cango[l])]&&mps[mp(cango[l],c)]) continue;
                            if(only[c][0]==-1) continue;
                            if(k==i-1){
                                if(only[cango[l]][0]==-2){
                                    if(!mps[mp(cango[l],c)]){
                                        mps[mp(cango[l],c)]=1;
                                        add(cango[l],c);
//                                      printf("%d %d\n",cango[l],c);
                                    }
                                }
                                continue;
                            }
                            if(only[c][0]==i&&only[c][1]==j) continue;
                            if(mps[mp(c,cango[l])]) continue;
                            mps[mp(c,cango[l])]=1;
                            add(c,cango[l]);
//                          printf("%d %d\n",c,cango[l]);
                        }
                    }
                }
                for(int k=i+1;k<=n&&s[k][j]!='#';++k){
                    int c=col[k][j];
                    if(c){
                        for(int l=1;l<=4;++l){
                            if(cango[l]==-1) continue;
                            if(c==cango[l]) continue;
                            if(mps[mp(c,cango[l])]&&mps[mp(cango[l],c)]) continue;
                            if(only[c][0]==-1) continue;
                            if(k==i+1){
                                if(only[cango[l]][0]==-2){
                                    if(!mps[mp(cango[l],c)]){
                                        mps[mp(cango[l],c)]=1;
                                        add(cango[l],c);
//                                      printf("%d %d\n",cango[l],c);
                                    }
                                }
                                continue;
                            }
                            if(only[c][0]==i&&only[c][1]==j) continue;
                            if(mps[mp(c,cango[l])]) continue;
                            mps[mp(c,cango[l])]=1;
                            add(c,cango[l]);
//                          printf("%d %d\n",c,cango[l]);
                        }
                    }
                }
            }
        }
    }
    dis[1]=0;
    for(int i=2;i<=cnt;++i) dis[i]=INF;
    priority_queue<pair<int,int> > q2;
    q2.push(mp(0,1));
    while(!q2.empty()){
        int u=q2.top().second;
        q2.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q2.push(mp(-dis[v],v));
            }
        }
    }
    mps.clear();
    for(int i=1;i<=ecnt;++i) e[i]=edge{0,0};
    ecnt=0;
    for(int i=1;i<=cnt;++i) hd[i]=0;
    cnt=0;
}
int main(){
    int T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)
            scanf("%s",s[i]+1);
        if(s[1][1]!='.'||s[n][n]!='.')
            return 0;
        for(int i=0;i<=n+1;++i)
            for(int j=0;j<=n+1;++j)
                col[i][j]=0;
        for(int i=0;i<=n+1;++i) s[i][0]=s[i][n+1]='#';
        for(int i=0;i<=n+1;++i) s[0][i]=s[n+1][i]='#';
        bfs();
//        for(int i=0;i<=n+1;++i){
//          for(int j=0;j<=n+1;++j){
//              printf("%d ",col[i][j]);
//          }
//          puts("");
//      }
        if(dis[col[n][n]]==INF) puts("-1");
        else printf("%d\n",dis[col[n][n]]*2);
    }
    return 0;
}

后记

其实一开始出题人 std 挂掉了，漏考虑了一次判断，结果新造的数竟然卡不掉错误的 std，在写题解时才发现自己手造的数据使得原来的 std 挂了。

在经过许多次对拍后发现卡不掉这种错法，只好作罢，把原 std 贴出来，希望各位能够把它给 hack 掉：

#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
inline int read(){
    int x=0;
    int ch=getchar(),f=0;
    while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
    while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return f?-x:x;
}
inline void write(int x,char end='\n'){
    if(x==0){
        putchar('0');
        putchar(end);
        return;
    }
    if(x<0) putchar('-'),x=-x;
    int st[70],sr=0;
    while(x){
        st[sr++]=x%10;
        x/=10;
    }
    while(sr--) putchar(st[sr]+48);
    putchar(end);
    return;
}
const int N=2005,INF=2e9;
const int M=2500005,M2=5000005;
const int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
int n;
char s[N][N];
int dis[N];
int col[N][N];
int head,tail;
struct node{
    int x,y;
};
struct edge{
    int to,nxt;
}e[M2];
int hd[M2],ecnt;
inline void add(int u,int v){
    e[++ecnt].to=v;
    e[ecnt].nxt=hd[u];
    hd[u]=ecnt;
}
node q[M2];
int cango[10],only[M2][2];
#define mp make_pair
map<pair<int,int>,bool> mps;
inline void bfs(){
    int cnt=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(s[i][j]=='.'&&!col[i][j]){
                head=1,tail=0;
                ++cnt;
                q[++tail]=(node{i,j});
                while(head<=tail){
                    node h=q[head++];
                    int x=h.x,y=h.y;
                    col[x][y]=cnt;
                    for(int i=0;i<4;++i){
                        int tx=x+dx[i],ty=y+dy[i];
                        if(s[tx][ty]!='.') continue;
                        if(!col[tx][ty]){
                            col[tx][ty]=cnt;
                            q[++tail]=(node{tx,ty});
                        }
                    }
                }
            }
        }
    }
    for(int i=1;i<=cnt;++i) only[i][0]=only[i][1]=-1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(col[i][j]){
                int g=col[i][j];
                if(s[i-1][j]=='#'){
                    if(only[g][0]==-1){
                        only[g][0]=i-1;
                        only[g][1]=j;
                    }
                    else
                        only[g][0]=only[g][1]=-2;
                }
                if(s[i+1][j]=='#'){
                    if(only[g][0]==-1){
                        only[g][0]=i+1;
                        only[g][1]=j;
                    }
                    else
                        only[g][0]=only[g][1]=-2;
                }
                if(s[i][j-1]=='#'){
                    if(only[g][0]==-1){
                        only[g][0]=i;
                        only[g][1]=j-1;
                    }
                    else
                        only[g][0]=only[g][1]=-2;
                }
                if(s[i][j+1]=='#'){
                    if(only[g][0]==-1){
                        only[g][0]=i;
                        only[g][1]=j+1;
                    }
                    else
                        only[g][0]=only[g][1]=-2;
                }
            }
        }
    }
    for(int i=0;i<=n+1;++i){
        for(int j=0;j<=n+1;++j){
            if(s[i][j]=='#'){
//              printf("now judging:%d %d\n",i,j);
                for(int k=1;k<=4;++k) cango[k]=-1;
                if(i<n&&col[i+1][j]) cango[1]=col[i+1][j];
                if(i>1&&col[i-1][j]) cango[2]=col[i-1][j];
                if(j<n&&col[i][j+1]) cango[3]=col[i][j+1];
                if(j>1&&col[i][j-1]) cango[4]=col[i][j-1];
                for(int k=j-1;k>=1&&s[i][k]!='#';--k){
                    int c=col[i][k];
                    if(c){
                        for(int l=1;l<=4;++l){
                            if(cango[l]==-1) continue;
                            if(c==cango[l]) continue;
                            if(mps[mp(c,cango[l])]&&mps[mp(cango[l],c)]) continue;
                            if(only[c][0]==-1) continue;
                            if(k==j-1){
                                if(only[cango[l]][0]==-2){
                                    if(!mps[mp(cango[l],c)]){
                                        mps[mp(cango[l],c)]=1;
                                        add(cango[l],c);
                                    }
                                }
                                continue;
                            }
                            if(mps[mp(c,cango[l])]) continue;
                            mps[mp(c,cango[l])]=1;
                            add(c,cango[l]);
//                          printf("%d %d\n",c,cango[l]);
                        }
                    }
                }
                for(int k=j+1;k<=n&&s[i][k]!='#';++k){
                    int c=col[i][k];
                    if(c){
                        for(int l=1;l<=4;++l){
                            if(cango[l]==-1) continue;
                            if(c==cango[l]) continue;
                            if(mps[mp(c,cango[l])]&&mps[mp(cango[l],c)]) continue;
                            if(only[c][0]==-1) continue;
                            if(k==j+1){
                                if(only[cango[l]][0]==-2){
                                    if(!mps[mp(cango[l],c)]){
                                        mps[mp(cango[l],c)]=1;
                                        add(cango[l],c);
                                    }
                                }
                                continue;
                            }
                            if(mps[mp(c,cango[l])]) continue;
                            mps[mp(c,cango[l])]=1;
                            add(c,cango[l]);
//                          printf("%d %d\n",c,cango[l]);
                        }
                    }
                }
                for(int k=i-1;k>=1&&s[k][j]!='#';--k){
                    int c=col[k][j];
                    if(c){
                        for(int l=1;l<=4;++l){
                            if(cango[l]==-1) continue;
                            if(c==cango[l]) continue;
                            if(mps[mp(c,cango[l])]&&mps[mp(cango[l],c)]) continue;
                            if(only[c][0]==-1) continue;
                            if(k==i-1){
                                if(only[cango[l]][0]==-2){
                                    if(!mps[mp(cango[l],c)]){
                                        mps[mp(cango[l],c)]=1;
                                        add(cango[l],c);
                                    }
                                }
                                continue;
                            }
                            if(mps[mp(c,cango[l])]) continue;
                            mps[mp(c,cango[l])]=1;
                            add(c,cango[l]);
//                          printf("%d %d\n",c,cango[l]);
                        }
                    }
                }
                for(int k=i+1;k<=n&&s[k][j]!='#';++k){
                    int c=col[k][j];
                    if(c){
                        for(int l=1;l<=4;++l){
                            if(cango[l]==-1) continue;
                            if(c==cango[l]) continue;
                            if(mps[mp(c,cango[l])]&&mps[mp(cango[l],c)]) continue;
                            if(only[c][0]==-1) continue;
                            if(k==i+1){
                                if(only[cango[l]][0]==-2){
                                    if(!mps[mp(cango[l],c)]){
                                        mps[mp(cango[l],c)]=1;
                                        add(cango[l],c);
                                    }
                                }
                                continue;
                            }
                            if(mps[mp(c,cango[l])]) continue;
                            mps[mp(c,cango[l])]=1;
                            add(c,cango[l]);
//                          printf("%d %d\n",c,cango[l]);
                        }
                    }
                }
            }
        }
    }
    dis[1]=0;
    for(int i=2;i<=cnt;++i) dis[i]=INF;
    priority_queue<pair<int,int> > q2;
    q2.push(mp(0,1));
    while(!q2.empty()){
        int u=q2.top().second;
        q2.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                q2.push(mp(-dis[v],v));
            }
        }
    }
    mps.clear();
    for(int i=1;i<=ecnt;++i) e[i]=edge{0,0};
    ecnt=0;
    for(int i=1;i<=cnt;++i) hd[i]=0;
    cnt=0;
}
int main(){
    freopen("portal.in","r",stdin);
    freopen("std2.out","w",stdout);
    int T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)
            scanf("%s",s[i]+1);
        if(s[1][1]!='.'||s[n][n]!='.')
            return 0;
        for(int i=0;i<=n+1;++i)
            for(int j=0;j<=n+1;++j)
                col[i][j]=0;
        for(int i=0;i<=n+1;++i) s[i][0]=s[i][n+1]='#';
        for(int i=0;i<=n+1;++i) s[0][i]=s[n+1][i]='#';
        bfs();
//        for(int i=0;i<=n+1;++i){
//          for(int j=0;j<=n+1;++j){
//              printf("%d ",col[i][j]);
//          }
//          puts("");
//      }
        if(dis[col[n][n]]==INF) puts("-1");
        else printf("%d\n",dis[col[n][n]]*2);
    }
    return 0;
}