disx1,y1,x2,y2 表示 M 到了 (x1,y1) 位置,G 到了 (x2,y2) 位置的最小距离,qu 数组是我模拟的队列,qu1/2/3/4 分别表示队列中存储的 x1,y1,x2,y2。
但我这个宽搜为啥错了?调了一下午+半个晚上,求助……
样例能过
#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;
}