Hamako Online Judge #097 ukuku09: 005 - devilswalk

,

$5$完で$6$位。やったね。

solution

隣接行列を$T$乗する。$O((WH)^3 \log T)$。速めの行列積を書けば通る。

implementation

#include <array>
#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
bool is_on_field(int y, int x, int h, int w) { return 0 <= y and y < h and 0 <= x and x < w; }

constexpr int max_h = 16;
constexpr int max_w = 16;
constexpr int mod = 1e9+7;
using type = array<array<int, max_h * max_w>, max_h * max_w>;
type append(type const & a, type const & b) {
    type tb;
    repeat (i, max_h * max_w) {
        repeat (j, max_h * max_w) {
            tb[i][j] = b[j][i];
        }
    }
    type c;
    repeat (i, max_h * max_w) {
        repeat (j, max_h * max_w) {
            ll acc = 0;
            repeat (k, max_h * max_w) {
                acc += a[i][k] *(ll) tb[j][k] % mod;
            }
            c[i][j] = acc % mod;
        }
    }
    return c;
}

int main() {
    int w, h, t; scanf("%d%d%d", &w, &h, &t);
    array<array<bool, max_h>, max_w> object = {};
    repeat (y, max_h) repeat (x, max_w) {
        object[y][x] = not is_on_field(y, x, h, w);
    }
    int object_count; scanf("%d", &object_count);
    repeat (i, object_count) {
        int x, y; scanf("%d%d", &x, &y); -- x; -- y;
        object[y][x] = true;
    }
    type e = {};
    repeat (y, h) repeat (x, w) {
        if (object[y][x]) continue;
        repeat (i, 4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (not is_on_field(ny, nx, h, w)) continue;
            if (object[ny][nx]) continue;
            e[y * max_w + x][ny * max_w + nx] += 1;
        }
    }
    type result = {};
    repeat (y, h) repeat (x, w) {
        if (object[y][x]) continue;
        result[y * max_w + x][y * max_w + x] = 1;
    }
    for (int i = 1; i <= t; i <<= 1) {
        if (t & i) {
            result = append(result, e);
        }
        e = append(e, e);
    }
    int query; scanf("%d", &query);
    while (query --) {
        int sx, sy, gx, gy; scanf("%d%d%d%d", &sx, &sy, &gx, &gy); -- sx; -- sy; -- gx; -- gy;
        printf("%d\n", result[sy * max_w + sx][gy * max_w + gx]);
    }
    return 0;
}