山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

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

感想

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

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