[白俊]2468安全区域

問題とI/O

質問へのアクセス

初めて問題に近づいたとき,全部で3段階に分けて問題を解いた.
bfsは

入力配列を巡回し、安全領域

を表示する.

セキュリティ領域を表示するシーケンス

各巡視

が領域をロックしていない場合、bfsを返し、カウント

.
上記の3つのステップを領域の高さで繰り返し、計算した数字のうち、最大停止した数字がこの問題の答えです.
その後解答を提出したところ、解答は成功した(実は正しいとは思わなかった)

コードの長さはかなり長く、成功しましたが、メモリと時間の観点からは効率が低いと思います.
そのため、再考の結果、第3段階では安全区域を明記する必要はないと思います.なぜなら、未アクセス領域において、水の高さよりも高い領域を巡回すると考えられる場合、既存の1,2ステップを一度に実現することができるからである.
これに基づいて再実現し、メモリと時間を節約し、成功したプールを再実現しました.

インプリメンテーションコード

初めての試み

import java.util.*;
import java.io.*;

class Reg {
    int x;
    int y;

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

public class Main {
    static int N;
    static int max = 0;
    static Integer[][] reg;
    static boolean[][] check;
    static boolean[][] got;
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, -1, 0, 1 };

    static int solve() {
        int count = 0;

        for (int i = 0; i < max; i++) {
            check = new boolean[N][N];
            got = new boolean[N][N];

            bfs(i);

            count = find_max(count);
        }

        return count;
    }

    static void bfs(int i) {
        Queue<Reg> q = new LinkedList<Reg>();
        q.add(new Reg(0, 0));

        while (!q.isEmpty()) {
            Reg temp = q.remove();

            for (int j = 0; j < 4; j++) {
                int x = temp.x + dx[j];
                int y = temp.y + dy[j];

                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (!got[x][y]) {
                        if (reg[x][y] <= i) {
                            check[x][y] = true;
                        }
                        q.add(new Reg(x, y));
                        got[x][y] = true;
                    }
                }
            }
        }
    }

    static int find_max(int count) {
        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!check[i][j]) {
                    check_true(i, j);
                    result++;
                }
            }
        }
        return Math.max(count, result);
    }

    static void check_true(int tx, int ty) {
        Queue<Reg> q = new LinkedList<Reg>();
        q.add(new Reg(tx, ty));

        while (!q.isEmpty()) {
            Reg temp = q.remove();

            for (int j = 0; j < 4; j++) {
                int x = temp.x + dx[j];
                int y = temp.y + dy[j];

                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (!check[x][y]) {
                        check[x][y] = true;
                        q.add(new Reg(x, y));
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        reg = new Integer[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int j = 0;
            while (st.hasMoreTokens()) {
                int temp = Integer.parseInt(st.nextToken());
                if (temp > max)
                    max = temp;
                reg[i][j] = temp;
                j++;
            }
        }

        System.out.println(solve());
    }
}

二次試行

import java.util.*;
import java.io.*;

class Reg {
    int x;
    int y;

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

public class bj2468 {
    static int N;
    static Integer[][] reg;
    static boolean[][] check;
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, -1, 0, 1 };

    static void dfs(int tx, int ty, int depth) {
        Queue<Reg> q = new LinkedList<Reg>();
        q.add(new Reg(tx, ty));

        while (!q.isEmpty()) {
            Reg temp = q.remove();

            for (int i = 0; i < 4; i++) {
                int x = temp.x + dx[i];
                int y = temp.y + dy[i];

                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (!check[x][y] && reg[x][y] > depth) {
                        q.add(new Reg(x, y));
                        check[x][y] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        reg = new Integer[N][N];

        int max = 0;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int j = 0;
            while (st.hasMoreTokens()) {
                int temp = Integer.parseInt(st.nextToken());
                if (temp > max)
                    max = temp;
                reg[i][j] = temp;
                j++;
            }
        }

        int result = 0;
        for (int depth = 0; depth < max; depth++) {
            check = new boolean[N][N];
            int count = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!check[i][j] && reg[i][j] > depth) {
                        dfs(i, j, depth);
                        count++;
                    }
                }
            }
            result = Math.max(count, result);
        }

        System.out.println(result);
    }
}