迷宫

C++14(g++5.4) 解法, 执行用时: 1139ms, 内存消耗: 174324K, 提交时间: 2020-04-18 17:07:43

#include<bits/stdc++.h>
using namespace std;
#define M 2005
char dr[M][M];
int s1,e1,s2,e2;
int fx[]={0,0,1,-1,1,-1,0,0};
int dis[M][M][2],n,m;
struct hh{
	int x,y,w;
}sk[M*M];
int q1[M],q2[M],mi[M][M],sl[M][M],fa1[M][M][2],fa2[M][M][2],ans1[M*M],ans2[M*M],cnt,pt1[M][M],pt2[M][M];
void Bfs(int x,int y,int f){
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)dis[i][j][f]=1e9;
	int l=1,r=0;sk[++r]=(hh){x,y,0};dis[x][y][f]=0;
	while(l<=r){
		hh p=sk[l++];
		for(int i=0;i<4;++i){
			int tx=p.x+fx[i],ty=p.y+fx[i+4];
			if(tx<1||tx>n||ty<1||ty>m)continue;
			if(dr[tx][ty]=='X')continue;
			if(p.w+1<dis[tx][ty][f]){
				dis[tx][ty][f]=p.w+1;
				fa1[tx][ty][f]=p.x;
				fa2[tx][ty][f]=p.y;
				sk[++r]=(hh){tx,ty,p.w+1};
			}
		}
	}
}
void dfs(int x,int y,int f){
	ans1[++cnt]=x-1;ans2[cnt]=y-1;
	if(fa1[x][y][f])dfs(fa1[x][y][f],fa2[x][y][f],f);
}
int main(){
	int d;scanf("%d%d%d",&n,&m,&d);
	for(int i=1;i<=n;++i)scanf("%s",dr[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(dr[i][j]=='S')s1=i,e1=j;
			else if(dr[i][j]=='T')s2=i,e2=j;
	Bfs(s1,e1,0);Bfs(s2,e2,1);
	int ans=dis[s2][e2][0];
	for(int i=1;i<=m;++i){
		int l=1,r=0;
		for(int j=1;j<=n;++j){
			while(r>=l&&dis[q1[r]][q2[r]][1]>dis[j][i][1])--r;
			q1[++r]=j;q2[r]=i;
			while(l<=r&&j-q1[l]>d+d)++l;
			mi[j][i]=dis[q1[l]][q2[l]][1];
			pt1[j][i]=q1[l];
			if(j==n){
				for(int k=d-1;k>=0;--k){
					while(l<=r&&j-q1[l]>k+d)++l;
					sl[k][i]=dis[q1[l]][q2[l]][1];
					pt2[k][i]=q1[l];
				}
			}
		}
	}
	int p1=s2,p2=e2,p3=s2,p4=e2;
	for(int i=1;i<=n-d;++i){
		int p=i+d,l=1,r=0;
		for(int j=1,tp=1;j<=m;++j){
			while(tp<=m&&abs(tp-j)<=d){
				while(r>=l&&mi[q1[r]][q2[r]]>mi[p][tp])--r;
				q1[++r]=p;q2[r]=tp;++tp;
			}
			while(l<=r&&j-q2[l]>d)++l;
			if(dis[i][j][0]+mi[q1[l]][q2[l]]+1<ans){
				ans=dis[i][j][0]+mi[q1[l]][q2[l]]+1;
				p1=i,p2=j;p3=pt1[q1[l]][q2[l]];p4=q2[l];
			}
		}
	}
	for(int i=max(1,n-d+1);i<=n;++i){
		int p=n-i,l=1,r=0;
		for(int j=1,tp=1;j<=m;++j){
			while(tp<=m&&abs(tp-j)<=d){
				while(r>=l&&sl[p][q2[r]]>sl[p][tp])--r;
				q2[++r]=tp;++tp;
			}
			while(l<=r&&j-q2[l]>d)++l;
			if(dis[i][j][0]+sl[p][q2[l]]+1<ans){
				ans=dis[i][j][0]+sl[p][q2[l]]+1;
				p1=i,p2=j;p3=pt2[p][q2[l]],p4=q2[l];
			}
		}
	}
	if(ans==1e9){
		puts("-1");
		return 0;
	}
	printf("%d\n",ans);
	dfs(p1,p2,0);
	for(int i=cnt;i>=1;--i)printf("%d %d\n",ans1[i],ans2[i]);
	cnt=0;
	dfs(p3,p4,1);
	for(int i=1;i<=cnt;++i){
		if(p1==p3&&p2==p4&&i==1)continue;
		printf("%d %d\n",ans1[i],ans2[i]);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 748ms, 内存消耗: 154956K, 提交时间: 2020-04-18 14:30:44

#include<bits/stdc++.h>
using namespace std;
#define N 2003
bool Bar;
int n,m,a,sx,sy,ex,ey,K[N][N],x,y,b,now;
int A_F[N][N],B_F[N][N],head,tail,k,r;
int Dis[N*N*2],Fr[N*N*2],Mk[N][N][2];
int Rx[5]= {0,0,-1,1};
int Ry[5]= {-1,1,0,0};
struct V {
	int x,y,k;
} Q[N*N*2],q;
char S[N];
bool Ka;
int Find_a(int i,int j) {
	return A_F[i][j]==j?j:A_F[i][j]=Find_a(i,A_F[i][j]);
}
int Find_b(int i,int j) {
	return B_F[i][j]==i?i:B_F[i][j]=Find_b(B_F[i][j],j);
}
int main() {
//	printf("%lf\n",(&Ka-&Bar)/1024.0/1024.0);
//	freopen("A.in","r",stdin);
//	freopen("try.out","w",stdout);
	scanf("%d %d %d",&n,&m,&a);
	for(int i=1; i<=n; ++i) {
		scanf("%s",S+1);
		for(int j=1; j<=m; ++j) {
			if(S[j]=='S')sx=i,sy=j;
			else if(S[j]=='T')ex=i,ey=j;
			else K[i][j]=S[j]=='X';
		}
	}
	for(int i=1; i<=n; ++i)for(int j=1; j<=m+1; ++j)A_F[i][j]=j;
	for(int i=1; i<=n+1; ++i)for(int j=1; j<=m; ++j)B_F[i][j]=i;
	Q[tail=1]=(V)<%sx,sy,0%>,Mk[sx][sy][0]=1;
	while(head<tail) {
		q=Q[++head];
		for(int z=0; z!=4; ++z) {
			x=q.x+Rx[z],y=q.y+Ry[z];
			if(x&&y&&x<=n&&y<=m&&!Mk[x][y][q.k]&&!K[x][y]) {
				Mk[x][y][q.k]=tail+1,Dis[tail+1]=Dis[head]+1;
				Q[++tail]=(V)<%x,y,q.k%>,Fr[tail]=head;
			}
		}
		if(q.k)continue;
		r=min(m,q.y+a);
		for(int j=Find_a(q.x,max(1,q.y-a)); j<=r;) {
			b=min(n,q.x+a);
			for(int k=Find_b(max(1,q.x-a),j); k<=b;) {
//				printf("%d %d %d %d %d\n",q.x,q.y,j,k,a);
				if(!Mk[k][j][1]&&!K[k][j]) {
					Mk[k][j][1]=tail+1,Dis[tail+1]=Dis[head]+1;
					Q[++tail]=(V)<%k,j,1%>,Fr[tail]=head;
				}
				B_F[k][j]=k+1,k=Find_b(k,j);
			}
			A_F[q.x][j]=j+1,j=Find_a(q.x,j);
		}
	}
	if(Mk[ex][ey][1]||Mk[ex][ey][0]) {
		if(Mk[ex][ey][0])now=Mk[ex][ey][0];
		if(!now||(Dis[now]>Dis[Mk[ex][ey][1]]&&Mk[ex][ey][1]))now=Mk[ex][ey][1];
		printf("%d\n",Dis[now]);
		while(now) Q[tail--]=Q[now],now=Fr[now];
		for(int i=tail+1; i<=head; ++i) {
			printf("%d %d\n",Q[i].x-1,Q[i].y-1);
		}
	} else puts("-1");
	return 0;
}

详情