洛谷P3855-[TJOI2008]Binary Land(BFS)

简介: 洛谷P3855-[TJOI2008]Binary Land(BFS)

题目背景:


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;
}

相关文章
|
7月前
|
机器学习/深度学习 安全 Java
hdu-1596-find the safest road(dijkstra)
hdu-1596-find the safest road(dijkstra)
46 0
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
147 0
|
存储 容器
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
华为机试HJ41:称砝码(深度优先遍历dfs-Depth First Search)
158 0
|
机器学习/深度学习 存储 C++
【PAT甲级 - C++题解】1102 Invert a Binary Tree
【PAT甲级 - C++题解】1102 Invert a Binary Tree
84 0
|
机器学习/深度学习 C++
【PAT甲级 - C++题解】1151 LCA in a Binary Tree
【PAT甲级 - C++题解】1151 LCA in a Binary Tree
78 0
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)
洛谷P3009-[USACO11JAN]Profits S(DP-最大子段和)
洛谷P3009-[USACO11JAN]Profits S(DP-最大子段和)
洛谷P3009-[USACO11JAN]Profits S(DP-最大子段和)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
|
移动开发
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)