AtCoder Grand Contest 014: C - Closed Rooms

,

http://agc014.contest.atcoder.jp/tasks/agc014_c

誤読。問題文が多少難しいとはいえ、A問題ぐらいには簡単だし$700$点でなくて$300$点でよさそう。

solution

$1$回目の魔法では開いた部屋しか移動できない。$2$回目以降の魔法では直前の魔法で通る部屋を開いておくことで、任意の部屋を移動可能。 そのようにBFSなりをする。$O(HW)$。

implementation

BFS部分がコピペで汚らしい。距離と$K$を比較して分岐する、$2$回目以降は最短経路つまり直線しか移動しないのでBFSしない、などすれば綺麗になるはず。

#include <cstdio>
#include <vector>
#include <queue>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
struct point_t { int y, x; };
const int inf = 1e9+7;

int main() {
    // input
    int h, w, k; scanf("%d%d%d", &h, &w, &k);
    auto closed = vectors(h, w, bool());
    point_t start;
    repeat (y,h) repeat (x,w) {
        char c; scanf(" %c", &c);
        closed[y][x] = c == '#';
        if (c == 'S') {
            start.y = y;
            start.x = x;
        }
    }
    // solve
    point_t goal = { -1, -1 };
    auto is_on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; };
    auto is_goal = [&](int y, int x) { return y == 0 or y == h-1 or x == 0 or x == w-1; };
    auto dist = vectors(h, w, inf);
    { // // bfs
        queue<point_t> que;
        dist[start.y][start.x] = 0;
        que.push(start);
        while (not que.empty()) {
            point_t p = que.front(); que.pop();
            if (is_goal(p.y, p.x)) {
                goal = p;
                break;
            }
            if (dist[p.y][p.x] == k) continue;
            repeat (i,4) {
                point_t q = p;
                q.y += dy[i];
                q.x += dx[i];
                if (not is_on_field(q.y, q.x)) continue;
                if (closed[q.y][q.x]) continue;
                if (dist[q.y][q.x] <= dist[p.y][p.x] + 1) continue;
                dist[q.y][q.x] = dist[p.y][p.x] + 1;
                que.push(q);
            }
        }
    }
    // // bfs
    if (goal.y == -1) {
        queue<point_t> que;
        repeat (y,h) repeat (x,w) {
            if (dist[y][x] != inf) {
                dist[y][x] = k;
                que.push((point_t) { y, x });
            }
        }
        while (not que.empty()) {
            point_t p = que.front(); que.pop();
            if (is_goal(p.y, p.x)) {
                goal = p;
                break;
            }
            repeat (i,4) {
                point_t q = p;
                q.y += dy[i];
                q.x += dx[i];
                if (not is_on_field(q.y, q.x)) continue;
                if (dist[q.y][q.x] <= dist[p.y][p.x] + 1) continue;
                dist[q.y][q.x] = dist[p.y][p.x] + 1;
                que.push(q);
            }
        }
    }
    // output
    assert (goal.y != -1);
    int result = (dist[goal.y][goal.x] + k - 1) / k;
    printf("%d\n", result);
    return 0;
}