CodeForces 198B Jumping on Walls(bfs || dfs)

       这道题纠结了快两天,刚开始因为地图的坐标纠结了好久,题意在下面代码中有,下面就说一下思路,我刚开始用bfs做的,卡在了不知道怎么比较当前位置和水位线的位置,一直不知道怎么记录水平面的位置,然后问了许多dalao,知道了在结构体中加了个step,用于记录走的步数,因为每走一步水位上升一格,所以步数step就相当于水位上升的高度,然后只需要比较step和你当前位置y就行了(只要step<=y就可走),刚开始我还把x和y弄反了,我说咋不输出结果....如果把地图竖起来的话还是比较好想的。下面把两种方法都贴上。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 100005;
char MAP[2][MAXN];
bool vis[2][MAXN];
struct Node{
  int x,y,step;
}Now,Next,S;
int n,m;

int bfs(){
  queue<Node> q;
  S.x = 0;               // 从左上角开始走
  S.y = 0;
  MAP[S.x][S.y] = 'X';   // 把起点标记一下
  S.step = 0;
  q.push(S);
  while(!q.empty()){
    Now = q.front();
    q.pop();
    if( Now.y > n){      // 当当前y坐标大于n的时候成功逃出
      return 1;
    }
    for(int i=0;i<3;i++){ // 三种方式
      Next.step = Now.step + 1;  // 表示水平面,记录走的步数就相当于水平面上升的高度
      if(i==0){
        Next.x = Now.x;
        Next.y = Now.y + 1;
      }
      if(i==1){
        Next.x = Now.x;
        Next.y = Now.y - 1;
      }
      if(i==2){
        Next.x = 1 - Now.x;
        Next.y = Now.y + m;
      }
      if(Next.y >= n){       // 这里需要特别判断一下,因为Next.y可能会跳出MAXN的范围而导致进不去下面的判断
        return 1;
      }
      if(Next.y >= 0 && Next.x >=0 && Next.x <= 1 && MAP[Next.x][Next.y] != 'X' && Next.step <= Next.y){  // 让step不大于当前坐标表示可走
      MAP[Next.x][Next.y] = 'X';
         q.push(Next);
       }
    }
  }
  return 0;
}
int main()
{
  while(~scanf("%d%d",&n,&m)){
    memset(MAP,0,sizeof(MAP));
    for(int i=0;i<2;i++){
      scanf("%s",MAP[i]);
    }
    if(bfs()) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}
/***
   [来源] CodeForces 198B
   [题目] Jumping on Walls
   [大意]
      有一个2*n的地图,有一个忍者从左上角的地方开始往右逃生,每次只能左右走一步,或者跳到另一行的当前位置+m的位置,
      每移动一次,水位就上升一格(被水淹的地方不能走),当忍者跳出地图算成功(X不可走,-可走)。
   [输入]
      7 3
      ---X--X
      -X--XX-
      6 2
      --X-X-
      X--XX-
   [输出]
      YES
      NO
*/

       下面是dfs的代码,注意判断条件需要注意顺序,先判断坐标是否越界,再判断地图是否能走,再判断这个点是否走过,

而忍者的移动也要注意顺序,优先往远的地方走,所以先走+m的,再走+1的最后走-1的。用dfs要简单些。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;
char MAP[2][MAXN];
int vis[2][MAXN];
int n,m,X,Y;
int dfs(int x,int y,int step){
  if(y < step||y<0||x<0||x>1) return 0;
  if(y > n) return 1;
  if(MAP[x][y]=='X') return 0;
  if(vis[x][y]==1) return 0;
  vis[x][y] = 1;
  if(dfs(1-x,y+m,step+1)) return 1;    // 优先走+m
  if(dfs(x,y+1,step+1)) return 1;
  if(dfs(x,y-1,step+1)) return 1;
  return 0;
}
int main()
{
  while(~scanf("%d%d",&n,&m)){
    memset(MAP,0,sizeof(MAP));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<2;i++){
      scanf("%s",MAP[i]);
    }
    int temp = dfs(0,0,0);
    if(temp==1) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券