求助
查看原帖
求助
857626
_RainCappuccino_楼主2023/5/28 18:29
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;
int n, k;
char a[MAXN][2];
bool vis[MAXN][2];
struct node {
	int h, id, s;
	node(int a, int b, int c) {
		h = a, id = b, s = c;
	}
};
void bfs(int s, int id) {
	node st = node(s, id, 0);
	queue<node> q;
	q.push(st);
	vis[s][id] = 1;
	while (!q.empty()) {
		node now = q.front();
		q.pop();
		int h = now.h, i = now.id, s = now.s;
		if (h > n) {
			puts("YES");
			return;
		}
		if (h <= s) continue;
		vis[h][i] = 1;
		if (a[h - 1][i] != 'X' && h - 1 >= 1 && !vis[h - 1][i]) {
			q.push(node(h - 1, i, s + 1));
		}
		if (a[h + 1][i] != 'X' && !vis[h + 1][i]) {
			q.push(node(h + 1, i, s + 1));
		}
		int next_id = i == 0 ? 1 : 0;
		if (a[h + k][next_id] != 'X' && !vis[h + 1][next_id]) {
			q.push(node(h + k, next_id, s + 1));
		}
	}
	puts("NO");
}
signed main() {
	ios::sync_with_stdio(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i][0];
	for (int i = 1; i <= n; i++) cin >> a[i][1];
	bfs(1, 0);
	return 0;
}
2023/5/28 18:29
加载中...