题目背景：
Binary Land是一款任天堂红白机上的经典游戏，讲述的是两只相爱的企鹅Gurin和Malon的故事。两只企鹅在一个封闭的迷宫中，你可以控制他们向上下左右四个方向移动。但是他们的移动有一个奇怪的规则，即如果你按“上”或“下”方向键，两只企鹅会同时向上移动或向下移动1格；如果你按“左”方向键，则Malon向左移动1格，同时Gurin向右移动1格；如果你按“右”方向键，则Malon向右移动1格，Gurin向左移动1格。当然，如果某只企鹅被障碍挡住，它就不会移动了。另外，在迷宫的某些格子处有蜘蛛网，如果任何一只企鹅进入这种格子，则游戏失败。两只企鹅不会相互阻挡，即在相向运动时他们可以“穿过”彼此，也可以同时处于同一格子里。迷宫的某个格子上有一颗红心，游戏的任务就是使两只企鹅同时到达这个格子。
网络异常，图片无法展示
|
题目描述：
请编写程序找出完成任务所需的最少的操作步数。如果无法完成目标，输出“no”。
输入格式：
第一行包含两个整数R, C 表示迷宫的长和宽。
按下来有R行，每行包含C个字符，描述了一个迷宫。其中’#’表示企鹅不能通过的障碍物，’X’表示蜘蛛网，’.’表示空地，’G’表示Gurin的初始位置，’M’表示Malon的初始位置，’T’表示终点位置。
输入数据保证标有’G’,’M’,’T’的格子分别只有一个，保证企鹅不可能走到迷宫以外。
输出格式：
输出只有一行，为最少的操作步数。如果不能完成任务，输出“no”。
样例输入：
4 7
#######
#..T..#
#G##M##
#######
样例输出：
4
说明/提示：
满足要求的一个操作序列为：上－右－左－左
3 ≤ R, C ≤ 30
AC Code：
#include<bits/stdc++.h> using namespace std; #define N 50 char s[N][N];//存入地图 bool vis[N][N][N][N];//标记数组，两只企鹅，需要开四维 //题中说上下两个方向，G、M两只企鹅是一样的 //左右两个方向，G、M两只企鹅则相反，所以注意数组中方向坐标的声明顺序 int dx1[]={0,0,1,-1};//dx1和dy1是G企鹅的方向数组 int dy1[]={1,-1,0,0}; int dx2[]={0,0,1,-1};//dx2和dy2是M企鹅的方向数组 int dy2[]={-1,1,0,0}; int n,m,sx1,sy1,sx2,sy2; struct node { int Mx,My,Gx,Gy,step; }; queue<node> q;//使用队列 int bfs(int sx1,int sy1,int sx2,int sy2) { node now,next;//队列的头和尾 now.Gx=sx1;//G企鹅的坐标 now.Gy=sy1; now.Mx=sx2;//M企鹅的坐标 now.My=sy2; now.step=0;//步数为0 q.push(now);//入队！！！ while(!q.empty()) {//保证队列不为空 now=q.front();//取队首 q.pop();//弹出队首 if(s[now.Gx][now.Gy]=='T'&&s[now.Mx][now.My]=='T') {//两只企鹅同时到达目标点T return now.step;//返回步数 } for(int i=0;i<4;i++) {//四个方向搜索 next.Gx=now.Gx+dx1[i];//G企鹅 next.Gy=now.Gy+dy1[i]; next.Mx=now.Mx+dx2[i];//M企鹅 next.My=now.My+dy2[i]; next.step=now.step+1; if(s[next.Gx][next.Gy]=='#') {//碰到障碍物，无法通过，此时仍为当前点的坐标 next.Gx=now.Gx; next.Gy=now.Gy; } if(s[next.Mx][next.My]=='#') {//同上 next.Mx=now.Mx; next.My=now.My; } //G、M两只企鹅没有越界，这个点没有走过，并且不能是蜘蛛网 if(next.Gx>=1&&next.Gx<=n&&next.Gy>=1&&next.Gy<=m &&next.Mx>=1&&next.Mx<=n&&next.My>=1&&next.My<=m &&vis[next.Gx][next.Gy][next.Mx][next.My]==false &&s[next.Gx][next.Gy]!='X'&&s[next.Mx][next.My]!='X') { vis[next.Gx][next.Gy][next.Mx][next.My]=true;//标记该点 q.push(next);//新的点入队 } } } return -1;//无法达到目标点T，返回-1 } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf(" %c",&s[i][j]);//%前面的空格确保地图可以完整输入 if(s[i][j]=='G') {//G企鹅的位置 sx1=i; sy1=j; } if(s[i][j]=='M') {//M企鹅的位置 sx2=i; sy2=j; } } } memset(vis,false,sizeof(vis));//清空标记数组 vis[sx1][sy1][sx2][sy2]=true;//标记两只企鹅此时所在位置坐标 int ans=bfs(sx1,sy1,sx2,sy2);//开始搜索 if(ans==-1) {//无法达到目标点T printf("no\n"); }else {//可以到达 printf("%d\n",ans); } return 0; }
