求助,万紫千红总是春,0分
查看原帖
求助,万紫千红总是春,0分
536337
eb0ycn楼主2024/1/31 19:26

disx1,y1,x2,y2\large dis_{x_1,y_1,x_2,y_2} 表示 M 到了 (x1,y1)(x_1,y_1) 位置,G 到了 (x2,y2)(x_2,y_2) 位置的最小距离,qu 数组是我模拟的队列,qu1/2/3/4qu_{1/2/3/4} 分别表示队列中存储的 x1,y1,x2,y2x_1,y_1,x_2,y_2。

但我这个宽搜为啥错了?调了一下午+半个晚上,求助……

样例能过

#include <cstdio>
using namespace std;
int R,C,dis[31][31][31][31],qu[810001][4],l=-1,r=-1,x1,y1,x2,y2,nx1,ny1,nx2,ny2,ex,ey,sx1,sx2,sy1,sy2,vis[31][31][31][31];
char ma[31][31];
const int dx1[4]={-1,0,1,0},dy1[4]={0,1,0,-1},dx2[4]={-1,0,1,0},dy2[4]={0,-1,0,1};
void bfs()
{
	qu[++r][0]=sx1,qu[r][1]=sy1,qu[r][2]=sx2,qu[r][3]=sy2;
	dis[sx1][sy1][sx2][sy2]=0;
	vis[sx1][sy1][sx2][sy2]=1;
	while(l<r)
	{
		x1=qu[++l][0],y1=qu[l][1],x2=qu[l][2],y2=qu[l][3];
		if(x1==x2&&y1==y2&&x1==ex&&y1==ey)
		{
			printf("%d",dis[x1][y1][x2][y2]);
			return ;
		}//两只企鹅同时到达终点
		for(int i=0;i<4;++i)
		{
			nx1=x1+dx1[i],nx2=x2+dx2[i],ny1=y1+dy1[i],ny2=y2+dy2[i];
			if(ma[nx1][ny1]=='X'||ma[nx2][ny2]=='X')continue;//碰到蜘蛛网就不能走了
			if(ma[nx1][ny1]=='#')nx1=x1,ny1=y1;
			if(ma[nx2][ny2]=='#')nx2=x2,ny2=y2;//一只企鹅碰到墙,要回来
			if(nx1==x1&&nx2==x2&&ny1==y1&&ny2==y2)continue;//但两只企鹅都碰墙就不行了
			if(!vis[nx1][ny1][nx2][ny2])vis[nx1][ny1][nx2][ny2]=1,dis[nx1][ny1][nx2][ny2]=dis[x1][y1][x2][y2]+1,qu[++r][0]=nx1,qu[r][1]=ny1,qu[r][2]=nx2,qu[r][3]=ny2;
		}
	}
	printf("no");
}
int main()
{
	scanf("%d%d",&R,&C);
	for(int i=1;i<=R;++i)
	{
		getchar();
		for(int j=1;j<=C;++j)
		{
			ma[i][j]=getchar();
			if(ma[i][j]=='G')sx2=i,sy2=j;
			if(ma[i][j]=='M')sx1=i,sy1=j;
			if(ma[i][j]=='T')ex=i,ey=j;
		}
	}
	bfs();
	return 0;
}

RE+WA

2024/1/31 19:26
加载中...