[BOJ 3055]脱出(Java)

質問する

邪悪な暗黒君主の李民赫はついに魔法の珠を手に入れ、その能力を実験するために近くのティムの森で洪水を起こそうとした.この森にはハリネズミが住んでいる.ハリネズミはできるだけ早く親友のビーバーの巣に逃げて洪水を避けようとした.
ティムの森の地図はR行C列で構成されています.「空いているところは」.水が満ちる地域は「*」、石は「X」と表示されます.ビーバーの穴は「D」で、ハリネズミの位置は「S」と表示されています.
ハリネズミは毎分、現在のグリッドに隣接する4つのグリッドの1つに移動できます.(上、下、右、左)水も毎分空の格子に広がっています.水のある格子に隣接するスペース(少なくとも1つのエッジを共有する)は水になります.水とハリネズミは石を通ることができない.また、ハリネズミは水で満たされたエリアに移動することができず、水もタヌキの巣に移動することができません.
ティムの森の地図を手に入れるときは、ハリネズミがタヌキの巣に安全に移動するのに要する最小時間を求めるプログラムを作成してください.
ハリネズミは予定の水満室に移動できません.つまり、ハリネズミは次の授業で予定の水満の場所に移動できません.移動できるとハリネズミが水に落ちるからだ.

入力

最初の行は、50以下の自然数RおよびCを与える.
「次のR行では、ティダンの森の地図が与えられ、質問で説明した文字だけが与えられます.」D'と'S'は一つだけ

しゅつりょく

1行目の出力ハリネズミはタヌキの穴に移動できる最速時間です.タヌキの巣窟まで安全に移動できない場合は「KAKTUS」を出力します.

方法

ハリネズミの移動だけでなく、水の移動も考えなければなりません.

質問には「水が上がったところでハリネズミは移動できない」と書かれているので、まず海水を移動してからハリネズミを移動しなければなりません.

メモリをさらに削減するには、従来のBFS問題でよく使用されているアクセス先の配列を格納するのではなく、既存のグラフィックを使用します.水が移動できる場合(空の空間とハリネズミが通る位置)、ハリネズミが移動できる場合(空の空間と到着場所)、それらを分けることができます.

1分後、水とハリネズミが移動した場合、到着位置がハリネズミ「S」になったかどうかを確認します.ハリネズミが到着した場合は、while出力結果の視覚から逃れ、ハリネズミが到着できない場合は「KAKTUS」を出力します.

に感謝

ハリネズミが通った道は水で覆われるはずだ!ハリネズミはこの位置ではなく通過する可能性があります.

ソースコード

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

public class Escape {

    static int r, c;
    static char[][] board;
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};
    static int end_r, end_c;

    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(" ");
        r = Integer.parseInt(input[0]);
        c = Integer.parseInt(input[1]);
        board = new char[r][c];
        ArrayDeque<Node> water = new ArrayDeque<>();
        ArrayDeque<Node> hedgehog = new ArrayDeque<>();

        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < c; j++) {
                if (line.charAt(j) == 'S') {
                    hedgehog.offer(new Node(i, j));
                } else if (line.charAt(j) == '*') {
                    water.offer(new Node(i, j));
                } else if (line.charAt(j) == 'D') {
                    board[i][j] = line.charAt(j);
                    end_r = i; end_c = j;
                }
                board[i][j] = line.charAt(j);

            }
        }

        boolean result = false;
        int cnt = 0;

        while (!hedgehog.isEmpty()) {
            cnt++;
            oneMinute(water, hedgehog);
      
            if (board[end_r][end_c] == 'S') {
                result = true;
                break;
            }
        }

        System.out.println(result ? cnt : "KAKTUS");
    }

    public static void oneMinute(ArrayDeque<Node> water, ArrayDeque<Node> hedgehog) {
        int wSize = water.size();
        int hSize = hedgehog.size();

        // 미리 바다를 늘려주기
        for (int i = 0; i < wSize; i++) {
            Node now = water.removeFirst();
            for (int j = 0; j < 4; j++) {
                int tmpx = now.x + dx[j];
                int tmpy = now.y + dy[j];
                if (0 <= tmpx && tmpx < r && 0 <= tmpy && tmpy < c && (board[tmpx][tmpy] == '.' || board[tmpx][tmpy] == 'S')) {
                    board[tmpx][tmpy] = '*';
                    water.offerLast(new Node(tmpx, tmpy));
                }
            }
        }

        // 고슴도치 이동
        for (int i = 0; i < hSize; i++) {
            Node now = hedgehog.removeFirst();
            for (int j = 0; j < 4; j++) {
                int tmpx = now.x + dx[j];
                int tmpy = now.y + dy[j];
                if (0 <= tmpx && tmpx < r && 0 <= tmpy && tmpy < c && (board[tmpx][tmpy] == '.' || board[tmpx][tmpy] == 'D')) {
                    board[tmpx][tmpy] = 'S';
                    hedgehog.offerLast(new Node(tmpx, tmpy));
                }
            }
        }
    }
}

結果