AtCoder Beginner Contest 020 C - 壁抜け - ヤマカサのプログラミング勉強日記

問題

C - 壁抜け

結構難しい問題だと思いました。三か月前にこの問題を解こうとして、ダイクストラ法を使うと知り、諦めてしまいました。

ダイクストラ法はAOJの問題で解いたことがありました。

[Aize Online Judge] ALDS1_12 - 山傘のプログラミング勉強日記

考え方

mmxsrup.hatenablog.com

上記のサイトを参考にすると、二分探索＆最短経路問題ということだそうです。ああ、二分探索を使うのかと感心しました。

二次元配列を一次元配列に落とす

マスの数は総計 $HW$ 個あります。なので、マスの数がノードの数となります。各マスの情報をマップと呼ぶことにします。

マップは二次元配列として読み込むことができますが、これを一次元配列に格納します。

$r$ 行 $c$ 列に対応する一次元配列の要素 $n$ は

$n = Wr + c$

となります。逆に、 $n$ に対応する $r, c$ は、

$r = \lfloor \dfrac{n}{H} \rfloor$

$c = n \mod W$

となります。

隣接行列

先程の一次元配列を $G$ とします。ノードが壁なら $1$ とし、それ以外は $0$ とします。

ノード $i$ に隣接するノードは、注目するノードの上下左右が存在するかを調べればよいので、

$i - 1, i +1, i - W, i + W$

が隣接ノードの候補となります。ただし、左端のノードは、 $i - 1$ とは隣接しおらず、右端のノードは、 $i + 1$ とは隣接していないことに注意します。

あとは、配列の要素番号の区間に隣接ノードが存在するかを調べればよいです。

二分探索

$x$ の値を二分探索します。

$l = 1$ , $r = T$ として初期値を与えます。二分探索を行うごとに隣接行列の値を変更する必要があります。

コード

import java.util.Scanner;

public class ProblemC {
    static int n;
    static long[][]M;
    static int[]G;
    static int sx, sy, gx, gy, H, W, ns;
    static long T;
    static long INF;
    static final int WHITE = 0;
    static final int GRAY = 1;
    static final int BLACK = 2;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        H = scan.nextInt();
        W = scan.nextInt();
        T = scan.nextLong();
        n = H * W;
        char[][] s = new char[H][W];
        G = new int[n];
        M = new long[n][n];
        INF = T + 1;
        for(int i = 0; i < H; i++) {
            String t = scan.next();
            for(int j = 0; j < W; j++) {
                char c = t.charAt(j);
                s[i][j] = t.charAt(j);
                if(c == 'S') {
                    sx = j;
                    sy = i;
                }
                if(c == 'G') {
                    gx = j;
                    gy = i;
                }
                if(c == '#') {
                    int p = W * i + j;
                    G[p] = 1;
                }
            }
        }
        scan.close();
        ns = W * sy + sx;
        dijkstra();
        long l = 1;
        long r = T;
        long mid = 0;
        while(r - l > 1) {
            mid = (l + r) / 2;
            initM(mid);
            long t = dijkstra();
            if(t > T) {
                r = mid;
            }else {
                l = mid;
            }
        }
        System.out.println(l);
    }
    static long dijkstra() {
        long minV;
        long []d = new long[n];
        int[]color = new int[n];
        for(int i = 0; i < n; i++) {
            d[i] = INF;
            color[i] = WHITE;
        }
        // 出発点
        d[ns] = 0;
        color[ns] = GRAY;
        while(true) {
            minV = INF;
            int u = -1;
            for(int i = 0; i < n; i++) {
                if(minV > d[i] && color[i] != BLACK) {
                    u = i;
                    minV = d[i];
                }
            }
            if(u == -1) break;
            color[u] = BLACK;
            for(int v = 0; v < n; v++) {
                if(d[v] > d[u] + M[u][v]) {
                    d[v] = d[u] + M[u][v];
                    color[v] = GRAY;
                }
            }
        }
        // ゴール
        int ng = W * gy + gx;
        return d[ng];
    }
    static void initM(long k) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                M[i][j] = INF;
            }
        }
        int m = H * W - 1;
        int[]di = {-1, 1, W, -W};
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j < 4; j++) {
                int ni = i + di[j];
                if(i % W == 0 && j == 0) {
                    continue;
                }
                if(i % W == W - 1 && j == 1) {
                    continue;
                }
                if(0 <= ni && ni <= m) {
                    if(G[ni] == 1) {
                        M[i][ni] = k;
                    }else {
                        M[i][ni] = 1;
                    }
                }
            }
        }
    }
}

感想

この問題を解くためにダイクストラ法を調べました。

複数の考え方が必要な良い問題だと思いました。