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