Untitled

mail@pastecode.io avatar
unknown
plain_text
25 days ago
3.2 kB
1
Indexable
Never
import java.util.Scanner;

public class IslandSplitter {
    static final int MAX = 102;
    static int n, m;
    static int[][] seawater = new int[MAX][MAX];
    static int Hmax = 0;
    static int[][] check = new int[MAX][MAX];
    static int[][] checkConnect = new int[MAX][MAX];
    static int extra;
    static int[] xAr = {1, 0, -1, 0}; // movement in x direction
    static int[] yAr = {0, -1, 0, 1}; // movement in y direction

    static void read(Scanner scanner) {
        Hmax = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                seawater[i][j] = scanner.nextInt();
                if (seawater[i][j] > Hmax) Hmax = seawater[i][j];
            }
        }
    }

    static void init() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                check[i][j] = 0;
                checkConnect[i][j] = 0;
            }
        }
    }

    static void floodFill(int i, int j) {
        check[i][j] = 1;
        for (int k = 0; k < 4; k++) {
            int X = j + xAr[k];
            int Y = i + yAr[k];
            if (X >= 1 && X <= m && Y >= 1 && Y <= n) {
                if (check[Y][X] == 0 && seawater[Y][X] <= extra) {
                    floodFill(Y, X);
                }
            }
        }
    }

    static void DFS(int i, int j) {
        checkConnect[i][j] = 1;
        for (int k = 0; k < 4; k++) {
            int X = j + xAr[k];
            int Y = i + yAr[k];
            if (X >= 1 && X <= m && Y >= 1 && Y <= n) {
                if (checkConnect[Y][X] == 0 && check[Y][X] == check[i][j]) {
                    DFS(Y, X);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = 0;
        while (true) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            if (n == 0 && m == 0) break;
            t++;
            read(scanner);
            boolean splits = false;
            for (int k = 0; k <= Hmax; k++) {
                extra = k;
                init();
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= m; j++) {
                        if ((i == 1 || i == n || j == 1 || j == m) && seawater[i][j] <= k && check[i][j] == 0) {
                            floodFill(i, j);
                        }
                    }
                }
                int countConnect = 0;
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= m; j++) {
                        if (checkConnect[i][j] == 0 && check[i][j] == 0) {
                            countConnect++;
                            DFS(i, j);
                        }
                    }
                }
                if (countConnect > 1) {
                    splits = true;
                    break;
                }
            }
            if (splits) {
                System.out.println("Case " + t + ": Island splits when ocean rises " + extra + " feet.");
            } else {
                System.out.println("Case " + t + ": Island never splits.");
            }
        }
        scanner.close();
    }
}
Leave a Comment