CodeForces - 198B Jumping on Walls

點選打開連結

題意：  跳躍忍者，兩個串就能看成兩個牆。然後往上蹦。

題解： 廣搜，深搜都可以。  重點是走過的不能走。不要以為水堵着就不能走了。

是以，bfs 超記憶體。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<vector>
using namespace std;
const int maxn=1e5+100;
int n,m,x,y,cnt;
char a[2][maxn];
int v[2][maxn];
struct node {
    int x,pos;
    int water;
}e,u,st;
int bfs(){
    st.x=1;st.pos=0;
    st.water=0;
    v[st.pos][st.x]=1;
    queue<node>que;
    que.push(st);
    while(!que.empty()){
        u=que.front();//printf("~~%d ~~%d~%d\n",u.pos,u.water,u.x);
        que.pop();
        e.pos=u.pos;
        e.x=u.x-1;e.water=u.water+1;
        if(e.x>0&&e.x>e.water&&a[e.pos][e.x]!='X'&&!v[e.pos][e.x]) {
            que.push(e);v[e.pos][e.x]=1;
        }
        e.x=u.x+1;if(e.x>n) return 1;
        if(e.x>0&&e.x>e.water&&a[e.pos][e.x]!='X'&&!v[e.pos][e.x]){
            que.push(e);v[e.pos][e.x]=1;
        }
        e.x=u.x+m;if(e.x>n) return 1;
        if(e.pos) e.pos=0;
        else e.pos=1;
        if(e.x>0&&e.x>e.water&&a[e.pos][e.x]!='X'&&!v[e.pos][e.x]){
            que.push(e);v[e.pos][e.x]=1;
        }
    }
    return 0;
}
int main(){

    while(~scanf("%d %d",&n,&m)){
        scanf("%s %s",a[0]+1,a[1]+1);
        if(bfs()) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}
           

深搜。  注意深搜裡的順序。 三個方向順序不一樣，就會錯。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<vector>
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int n,m,water;
char a[2][maxn];
int v[2][maxn];
int dfs(int pos,int j){
    if(j>n) return 1;
    if(a[pos][j]=='X'||j<water||v[pos][j]) return 0;
    v[pos][j]=1;
    water++;
    int f=dfs(pos,j-1)||dfs(1-pos,j+m)||dfs(pos,j+1);
    water--;
    return f;
}
int main(){

    scanf("%d %d",&n,&m);
        water=1;
        scanf("%s %s",a[0]+1,a[1]+1);
        if(dfs(0,1)) printf("YES\n");
        else printf("NO\n");
    return 0;
}