[BOJ 2573]氷山(Java)

質問する

地球温暖化で北極氷山が溶けている.図1に示すように、氷山を2次元アレイに表示します.氷山の各部分の高さ情報は,配列された各セルに正の整数として格納される.氷山以外の海に対応する格には0が格納されている.図1では、スペースはすべてゼロで埋め込まれていると思います.

氷山の高さは海水との接触が多い場所でより速く減少するため、配列中の氷山の各部分に対応する格子の高さは毎年、格子の中で東西南北4方向に付着する0の格子の個数を減少させる.ただし、各セルに格納される高さは0より小さくなりません.海水は湖水のように氷山に囲まれているかもしれない.従って、図1の氷山は、図2に示すように1年後に変形する.
図3は、図1の氷山の2年後の変化を示す.2 D配列では,東西南北方向の格子が互いに接続されている.したがって、図2の氷山は1つであり、図3の氷山は3つに分かれている.

氷山が1つ与えられた場合、プログラムを作成して、この氷山が2つ以上分離された最初の時間(年)を求めます.図1の氷山について、答えは2です.全てが溶けるまで2つ以上離さないと、プログラムは0を出力します.

入力

1行目では、2つの整数NとMは、2次元配列の行数と列数を表すスペースで区切られます.NとMは3以上300以下である.次のN行では、各行の間にスペースがあり、M個の整数は配列の各行を表します.各グリッドの値は0以上10以下です.配列では、氷山が占める格の個数、すなわち1以上の整数が占める格の個数が10000以下である.配列の最初の行と最後の行と最後の列は常に0で埋め込まれます.

しゅつりょく

1行目は氷山分離の最初の時間(年)を出力する.氷山が溶けるまで分離していない場合は0を出力します.

方法

氷山が2つ以上になるまで時間を稼ぐ必要があります.問題の前提から見ると、氷山は一度に溶けるか、割れるか、どちらかの状態で終わる.

今から氷山を溶かしてこの場合、2つの重要な情報を格納する必要があります.

BFSをブラウズ中に通過した場所

探索した氷山に連なる海の個数(融解が必要な氷山の量)

ナビゲーションの順序は次のとおりです.

現在位置で検出可能な氷山を上、下、左、右方向にキューに入れる.

の上、下、左、右方向に隣接する海の個数を計算します.

すべてのナビゲーションが完了すると、すべての場所をナビゲートし、「溶融」アレイに格納されている融解する必要がある氷山の位置と値が適用されます.

時間ごとに氷山が溶け続ける場合、氷山が2回ブラウズ(2つの部分に分かれている)されたり、1回すべて溶けたりすると、while繰り返し文は結果値を出力します.

に感謝

がアクセスする位置の配列と、融解する必要がある氷山量の配列を格納する.

ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;

public class Iceberg {

    static int n, m;
    static int[][] board;
    static int[][] melt;
    static boolean[][] visit;
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        board = new int[n][m];
        int result = 0;

        for (int i = 0; i < n; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(input[j]);
            }
        }
        br.close();

        while (true) {
            int cnt = 0;
            melt = new int[n][m];
            visit = new boolean[n][m];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!visit[i][j] && board[i][j] > 0) {
                        visit[i][j] = true;
                        melting(i, j);
                        cnt++;
                    }
                }
            }

            if (cnt == 0) {
                result = 0;
                break;
            } else if (cnt > 1) break;
            result++;
        }

        System.out.println(result);
    }

    public static void melting(int x, int y) {
        ArrayDeque<Node> dq = new ArrayDeque<>();
        dq.offerLast(new Node(x, y));

        while (!dq.isEmpty()) {
            Node now = dq.removeFirst();
            int sea = 0;
            for (int i = 0; i < 4; i++) {
                int tmpx = now.x + dx[i];
                int tmpy = now.y + dy[i];
                if (!visit[tmpx][tmpy] && board[tmpx][tmpy] > 0) {
                    dq.offerLast(new Node(tmpx, tmpy));
                    visit[tmpx][tmpy] = true;
                }
                if (board[tmpx][tmpy] <= 0) {
                    sea++;
                }
            }
            melt[now.x][now.y] = sea;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] -= melt[i][j];
            }
        }
    }
}

結果