-
Notifications
You must be signed in to change notification settings - Fork 0
/
Codeforces 199D.cpp
48 lines (43 loc) · 1.29 KB
/
Codeforces 199D.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
char game[2][100010];
bool valid(int row, int col){
if(row < 0 || col < 0 || row >= 2) return false;
return true;
}
bool BFS(int n, int k){
queue<pair<int, pair<int, int>>> cola;
bool visited[2][n];
memset(visited, false, sizeof(visited[0][0]) * 2 * n);
int rows[] = {0, 0, 1, -1}, cols[] = {1, -1, k, k};
visited[0][0] = true;
cola.push(make_pair(0, make_pair(0, 0)));
while(!cola.empty()){
int row = cola.front().second.first;
int col = cola.front().second.second;
int water = cola.front().first;
cola.pop();
for(int i = 0; i < 4; i++){
int nRow = row + rows[i];
int nCol = col + cols[i];
if(valid(nRow, nCol)){
if(nCol >= n) return true;
if(!visited[nRow][nCol] && game[nRow][nCol] != 'X' && nCol > water){
visited[nRow][nCol] = true;
cola.push(make_pair(water + 1, make_pair(nRow, nCol)));
}
}
}
}
return false;
}
int main(){
int n, k;
scanf("%d%d", &n, &k);
for(int i = 0; i < 2; i++) scanf("%s", &game[i]);
if(BFS(n, k)) printf("YES\n");
else printf("NO\n");
return 0;
}