Cod sursa(job #971899)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 10 iulie 2013 15:10:45
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
//#include <fstream>
using namespace std;
//ifstream f("wow.in");
//ofstream g("wow.out");
int nr,n,k;
#define LE 100666
#include <string>
string S[2];
int result;
pair<int,int> que[LE*10];
#define x first
#define y second
#define mp make_pair
int dp[2][LE];
bool viz[2][LE];

#define f cin
#define g cout

void BFS() {
    int i;

    for(i=1; i<=nr; ++i) {

        if (dp[que[i].x][que[i].y]>=que[i].y+1)
          continue;

        if (que[i].y+1>=n||que[i].y+k>=n) {
            result=dp[que[i].x][que[i].y]+1;
            break;
        }

        if (S[que[i].x][que[i].y+1]=='-'&&viz[que[i].x][que[i].y+1]==false) {
            que[++nr]=mp(que[i].x,que[i].y+1);
            dp[que[i].x][que[i].y+1]=dp[que[i].x][que[i].y]+1;
            viz[que[i].x][que[i].y+1]=true;
        }

        if (que[i].y-1>=0)
            if (S[que[i].x][que[i].y-1]=='-'&&viz[que[i].x][que[i].y-1]==false) {
                que[++nr]=mp(que[i].x,que[i].y-1);
                dp[que[i].x][que[i].y-1]=dp[que[i].x][que[i].y]+1;
                viz[que[i].x][que[i].y-1]=true;
            }


        if (S[que[i].x^1][que[i].y+k]=='-'&&viz[que[i].x^1][que[i].y+k]==false) {
            que[++nr]=mp(que[i].x^1,que[i].y+k);
            dp[que[i].x^1][que[i].y+k]=dp[que[i].x][que[i].y]+1;
            viz[que[i].x^1][que[i].y+k]=true;
        }
    }
}

int main() {
    f>>n>>k;
    f.get();
    f>>S[0]>>S[1];
    viz[0][0]=true;
    dp[0][0]=0;
    que[++nr]=mp(0,0);
    BFS();

    if (result!=0) g<<"YES";
    else g<<"NO";
    g<<'\n';



    return 0;
}