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

#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
*/

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