15011418730 LV 7 @ 2025-8-24 22:43:25

自动搬运

来自洛谷，原作者为

	andychen_2012 **

搬运于2025-08-24 22:43:25，当前版本为作者最后更新于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;
}

ID

8176

时间

3000ms

内存

128MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

【DMOI 官方题解】

解题思路

部分分

正解

解题代码

后记

[DMOI-R1] Portal

信息

1 条题解

自动搬运

以下是正文

【DMOI 官方题解】

解题思路

部分分

正解

解题代码

后记

[DMOI-R1] Portal

信息

还没有账户？

登录