RE求助
查看原帖
RE求助
394055
huangchuyang楼主2022/9/30 13:02
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,h,t=1,f[35][35][35][35];
char mp[50][50];
int dmx[]={1,-1,0,0};
int dmy[]={0,0,1,-1};
int dgx[]={1,-1,0,0};
int dgy[]={0,0,-1,1};
struct ab{
	int mx,my,gx,gy,s;
}q[5000005];
int main(){
//	memset(f,9,sizeof(f));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='G') q[1].gx=i,q[1].gy=j;
			if(mp[i][j]=='M') q[1].mx=i,q[1].my=j; 
//			printf("%c",mp[i][j]);
		}
	}
 	q[1].s=0,f[q[1].gx][q[1].gy][q[1].mx][q[1].my]=1;
//	printf("%d %d %d %d\n",q[1].gx,q[1].gy,q[1].mx,q[1].my);
	while(h<=t){
		
//		printf("1\n");
		int xg=q[++h].gx,yg=q[h].gy,xm=q[h].mx,ym=q[h].my,a=q[h].s;
//		printf("%d %d %d %d\n",q[h].gx,q[h].gy,q[h].mx,q[h].my);
		if(xg==xm&&yg==ym&&mp[xg][yg]=='T') {
			printf("%d",a);
			return 0;
		}
		for(int i=0;i<=3;i++){
			int ngx=xg+dgx[i],ngy=yg+dgy[i],nmx=xm+dmx[i],nmy=ym+dmy[i];
			
			if(ngx<=0||ngx>n||ngy<=0||ngy>m||nmx<=0||nmx>n||nmy<=0||nmy>m) continue;
			if(mp[ngx][ngy]=='X'||mp[nmx][nmy]=='X') continue;
			if(mp[ngx][ngy]=='#'&&mp[nmx][nmy]=='#') continue;
			if(f[ngx][ngy][nmx][nmy]) continue;
			if(mp[ngx][ngy]=='#'){
				q[++t].gx=xg,q[t].gy=yg,q[t].mx=nmx,q[t].my=nmy,q[t].s=a+1,f[xg][yg][nmx][nmy]=1;
			}
			else if(mp[nmx][nmy]=='#'){
				q[++t].gx=ngx,q[t].gy=ngy,q[t].mx=xm,q[t].my=ym,q[t].s=a+1,f[ngx][ngy][xm][ym]=1;
			}
			else{
				q[++t].gx=ngx,q[t].gy=ngy,q[t].mx=nmx,q[t].my=nmy,q[t].s=a+1,f[ngx][ngy][nmx][nmy]=1;
			}
		}
	}
	printf("no");
	return 0;
} 
2022/9/30 13:02
加载中...