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