0w1

CFR 198 1B. Jumping on Walls ( PFS )

Problem - B - Codeforces
Dijkstraみたいな感じでやればいいね。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXK = 1e5 + 5;

int n, k;

char w[ 2 ][ MAXN ];

struct State{
    int t, x, lv;
    State( int _t = -1, int _x = -1, int _lv = -1 ): t(_t), x(_x), lv(_lv){}
    bool operator < ( const State &oth ) const{
        return lv < oth.lv;
    }
};

int mint[ 2 ][ MAXN ];

void solve(){
    priority_queue< State > pq;
    memset( mint, 0x3f3f3f3f, sizeof(mint) );
    pq.push( State( mint[ 0 ][ 0 ] = 0, 0, 0 ) );
    while( !pq.empty() ){
        int t = pq.top().t;
        int x = pq.top().x;
        int lv = pq.top().lv;
        pq.pop();
        if( lv + 1 == n || lv + k >= n ) return (void)puts("YES");
        if( w[ x ][ lv + 1 ] == '-' )
            if( mint[ x ][ lv + 1 ] > mint[ x ][ lv ] + 1 )
                mint[ x ][ lv + 1 ] = mint[ x ][ lv ] + 1,
                pq.push( State( mint[ x ][ lv + 1 ], x, lv + 1 ) );
        if( w[ x^1 ][ lv + k ] == '-' )
            if( mint[ x^1 ][ lv + k ] > mint[ x ][ lv ] + 1 )
                mint[ x^1 ][ lv + k ] = mint[ x ][ lv ] + 1,
                pq.push( State( mint[ x^1 ][ lv + k ], x^1, lv + k ) );
        if( lv - 1 >= 0 && w[ x ][ lv - 1 ] == '-' )
            if( mint[ x ][ lv ] + 1 < lv )
                if( mint[ x ][ lv - 1 ] > mint[ x ][ lv ] + 1 )
                    mint[ x ][ lv - 1 ] = mint[ x ][ lv ] + 1,
                    pq.push( State( mint[ x ][ lv - 1 ], x, lv - 1 ) );
    }
    puts("NO");
}

int main(){
    scanf("%d%d", &n, &k);
    for( int i = 0; i < 2; ++i )
        scanf("%s", w[ i ]);
    solve();
    return 0;
}