[BOJ 16236]小さなサメ(Java)

質問する

N×Nサイズの空間にはM匹の魚と小さなサメが1匹います.スペース1×1サイズの正方形の格子に分けます.1つの格子には最大1匹の魚が存在する.
小さなサメも魚も大きさがあり、この大きさは自然数です.最初は小さいサメの大きさが2で、小さいサメは1秒程度で隣の1マスを移動します.
小さなサメは自分より大きい魚の格子を通ることができず、残りの格子は通ることができます.サメは自分より小さい魚しか食べられません.そのため、同じ大きさの魚は食べられませんが、魚の格子があって行けます.
サメがどこに移動するかを決める方法は以下の通りです.
空間に食べられる魚がなければ、サメはお母さんのサメに助けを求めます.もし魚が

食べられるなら、私はそれを食べに行きます.

の魚が1匹以上食べられるなら、一番近い魚を食べに行きます.

街は、サメがいる格子から魚がいる格子に移動する際に通過する格子の個数の最高値です.

街から近い魚が多いなら、一番上の魚、何匹も魚がいるなら、一番左の魚を食べます.

幼サメの移動に1秒かかると仮定し、魚を食べる時間がない.つまり、サメが魚が食べられる場所に移動すると、移動しながら魚を食べます.魚を食べたら、その一格は空いていました.

サメは自分の大きさと同じ数の魚を食べるたびに、大きさが1つ増えます.例えば、大きさ2の小さなサメが2匹の魚を食べる場合、大きさは3です.
空間状態にあるときは、小さなサメが数秒以内にお母さんのサメに助けを求めずに魚を食べることができるかどうかを見るプログラムを作成します.

入力

第1行は空間サイズN(2≦N≦20)を与える.
2行目から、N行スペースを与えた状態.空間の状態は0、1、2、3、4、5、6、9からなり、以下の意味を持つ.

0:スペース

1、2、3、4、5、6:格の中の魚の大きさ

9:小さなサメの位置
小さなサメが空間に1匹います.

しゅつりょく

最初の行はサメがお母さんのサメの助けを求めずに魚を食べる時間を出力します.

方法

問題のニーズを分析すると、実装とシミュレーションに近いBFSを感じることができます.しかし、私たちが簡単に解くBFSタイプではなく、サメが食べられるまで通りを思う存分行き来することができます.

考えを変えよう私たちはその時に最短距離の食べ物を探して食べればいいです.すなわち,BFSナビゲーションは餌探し時のみ行い,構造を変更して残りの部分をシミュレートした.

すべての通過可能な空間をナビゲートできる食べ物(eatable優先キュー)が1つもない場合は、経過した時間を0に戻します.

反対の食べ物があったら?食べ物を食べた後、その場所に一番近い食べ物を見つけてeat()を実行し、現在の時刻に食事に必要な時間を加えて戻ります.

に感謝

で同じ時点で1つ以上の食用食品が存在する場合、ランダムに選択された結果は異なる可能性がある.そのため、優先順位キューを使用して、一番上と左の食べ物を食べさせることを考慮する必要があります.

サメは食べられる個体ではありません!入力値を受け取ると、9(サメの位置)は単独の位置しか保存できず、黒板に置くことはできません.

ソースコード

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

public class BabyShark {

    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};
    static int n;
    static int[][] board;
    static int sharkSize = 2, sharkEat = 0;

    static class Shark implements Comparable<Shark>{
        int x;
        int y;

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

        @Override
        public int compareTo(Shark o) {
            if (this.x == o.x) {
                return this.y - o.y;
            }
            return this.x - o.x;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        int start_x = 0, start_y = 0;

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                int cur = Integer.parseInt(input[j]);
                if (cur == 9) {
                    start_x = i;
                    start_y = j;
                    continue;
                }
                board[i][j] = cur;
            }
        }

        System.out.println(eat(start_x, start_y));
    }

    public static int eat(int x, int y) {
        boolean[][] visit = new boolean[n][n];
        ArrayDeque<Shark> dq = new ArrayDeque<>();
        PriorityQueue<Shark> eatable = new PriorityQueue<>();
        int time = 0;

        dq.offerLast(new Shark(x, y));

        while (!dq.isEmpty() && eatable.isEmpty()) {
            time++;
            int size = dq.size();
            for (int i = 0; i < size; i++) {
                Shark now = dq.removeFirst();
                for (int j = 0; j < 4; j++) {
                    int tmpx = now.x + dx[j];
                    int tmpy = now.y + dy[j];
                    if (0 <= tmpx && tmpx < n && 0 <= tmpy && tmpy < n && !visit[tmpx][tmpy] && board[tmpx][tmpy] <= sharkSize) {
                        Shark next = new Shark(tmpx, tmpy);
                        if (board[tmpx][tmpy] < sharkSize && board[tmpx][tmpy] != 0) {
                            eatable.offer(next);
                        }
                        dq.offerLast(next);
                        visit[tmpx][tmpy] = true;
                    }
                }
            }
        }

        if (eatable.isEmpty()) return 0;

        Shark eatPoint = eatable.poll();
        board[eatPoint.x][eatPoint.y] = 0;
        sharkEat++;
        if (sharkEat == sharkSize) {
            sharkEat = 0;
            sharkSize++;
        }

        return eat(eatPoint.x, eatPoint.y) + time;
    }
}

結果