結果

問題 No.2328 Build Walls
ユーザー InTheBloom
提出日時 2025-07-10 08:14:13
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 319 ms / 3,000 ms
コード長 1,679 bytes
コンパイル時間 4,408 ms
コンパイル使用メモリ 173,480 KB
実行使用メモリ 14,976 KB
最終ジャッジ日時 2025-07-10 08:14:22
合計ジャッジ時間 9,195 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int H, W;
    readln.read(H, W);
    auto A = new int[][](H - 2);
    foreach (i; 0 .. H - 2) {
        A[i] = readln.split.to!(int[]);
    }

    auto cost = new int[][](H - 2, W);
    foreach (c; cost) {
        c[] = int.max;
    }
    auto pq = BinaryHeap!(Tuple!(int, int, int)[], "b[2] < a[2]")([]);

    foreach (i; 0 .. H - 2) {
        if (A[i][0] == -1) {
            continue;
        }
        pq.insert(tuple(i, 0, A[i][0]));
        cost[i][0] = A[i][0];
    }

    bool isIn (int y, int x) {
        return 0 <= y && y < H - 2 && 0 <= x && x < W;
    }

    while (!pq.empty()) {
        auto pos = pq.front();
        pq.removeFront();
        int y = pos[0], x = pos[1];
        int c = pos[2];

        foreach (dy; -1 .. 2) {
            foreach (dx; -1 .. 2) {
                int ny = y + dy;
                int nx = x + dx;

                if (!isIn(ny, nx) || A[ny][nx] == -1) {
                    continue;
                }
                int nc = c + A[ny][nx];
                if (nc < cost[ny][nx]) {
                    cost[ny][nx] = nc;
                    pq.insert(tuple(ny, nx, nc));
                }
            }
        }
    }

    /*
    writeln("--");
    cost.each!(v => writefln("%(%s %)", v));
    */

    int ans = int.max;
    foreach (i; 0 .. H - 2) {
        ans = min(ans, cost[i][W - 1]);
    }

    if (ans == int.max) {
        writeln(-1);
    }
    else {
        writeln(ans);
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0