Codeforces Round #125 (Div. 1) B : Jumping on Walls

問題概要

高さn(<10^5)の壁が左右それぞれにあり、いくつかの高さの壁には張り付くことができない。最初高さ1の左側の壁に張り付いている。1秒毎にひとつ下に行く、ひとつ上に行く、反対の壁の高さcurrent + kの位置に行く、のいずれかを選択できる。下から水位が毎秒1ずつ増加していく。高さn以上の部分に到達できるかどうか判定する問題。

解法

幅優先探索するだけでよい。

acceptされたコード

#include <cstdio>
#include <queue>
using namespace std;

const int MAX_N = (int)(1e5);

int N, K, L;
char buf[2][MAX_N + 1];
int dist[2][MAX_N + 1];

void init() {
	scanf("%d%d ", &N, &K);
	for (int i = 0; i < 2; ++i) {
		scanf(" %s ", buf[i]);
	}

}

bool solve() {
	for (int i = 0; i < 2; ++i) {
		fill(dist[i], dist[i] + MAX_N + 1, -1);
	}

	queue< pair<int,int> > que;
	dist[0][0] = 0;
	que.push( make_pair(0, 0) );

	for (;!que.empty();) {
		int n = que.front().second, which = que.front().first; que.pop();
		int nd = dist[which][n] + 1;
		if (n + 1 >= N || n + K >= N) {
			return true;
		}

		if (n > 0 && dist[which][n-1] == -1 && buf[which][n-1] != 'X' && nd <= n - 1) {
			dist[which][n-1] = nd;
			que.push( make_pair(which, n-1) );
		}
		if (n < N && dist[which][n+1] == -1 && buf[which][n+1] != 'X') {
			dist[which][n+1] = nd;
			que.push( make_pair(which, n+1) );
		}
		if (n + K < N && dist[which^1][n+K] == -1 && buf[which^1][n+K] != 'X') {
			dist[which^1][n+K] = nd;
			que.push( make_pair(which^1, n+K) );
		}
	}
	return false;
}

int main() {
	init();
	puts(solve() ? "YES" : "NO");

	return 0;
}