Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
3.4 kB
4
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, h, max, min;
	static int A[][] = new int[101][101];
	static int visit[][] = new int[101][101];
	static Queue queue = new Queue(2000000);
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("src/input.txt"));
		Scanner sc = new Scanner(System.in);
		int tc = 0;
		while (true) {
			tc++;
			n = sc.nextInt();
			m = sc.nextInt();

			if (n == 0 && m == 0)
				break;
			max = 0;
			min = 1000;

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					A[i][j] = sc.nextInt();
					if (max < A[i][j]) {
						max = A[i][j];
					}
					if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
						if (A[i][j] != 0 && min > A[i][j]) {
							min = A[i][j];
						}
					}
				}
			}

			boolean found = false;
			for (int k = min; k <= max && !found; k++) {
				for (int i = 0; i < n; i++) {
					for (int d = 0; d < n; d++) {
						for (int j = 0; j < m; j++) {
							visit[d][j] = 0;
						}
					}
					for (int j = 0; j < m; j++) {
						if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
							if (A[i][j] <= k) {
								queue.reset();
								queue.push(i);
								queue.push(j);
								visit[i][j] = 1;
								A[i][j] = 0;
								if (bfs(i, j, k)) {
									h = k;
									found = true;
								}
							}
						} else {
							continue;
						}
					}
				}
			}

			if (!found) {
				System.out.println("Case " + tc + ": " + "Island never splits.");
			} else {
				System.out.println("Case " + tc + ": " + "Island splits when ocean rises " + h + " feet.");
			}

		}
		sc.close();
	}

	private static boolean bfs(int x, int y, int k) {
		// TODO Auto-generated method stub
		int r, c;
		while (!queue.empty()) {
			r = queue.pop();
			c = queue.pop();
			for (int i = 0; i < 4; i++) {
				int nr = r + dx[i];
				int nc = c + dy[i];

				if (nr >= 0 && nc >= 0 && nr < n && nc < m && visit[nr][nc] == 0 && A[nr][nc] <= k) {
					visit[nr][nc] = 1;
					A[nr][nc] = 0;
					queue.push(nr);
					queue.push(nc);
				}
			}

		}
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (A[i][j] != 0 && visit[i][j] == 0) {
					cnt++;
					if (cnt == 2)
						return true;
					find(i, j);
				}
			}
		}

		return false;
	}

	private static void find(int x, int y) {
		// TODO Auto-generated method stub
		queue.reset();
		queue.push(x);
		queue.push(y);
		visit[x][y] = 1;
		int r, c;
		while (!queue.empty()) {
			r = queue.pop();
			c = queue.pop();

			for (int i = 0; i < 4; i++) {
				int nr = r + dx[i];
				int nc = c + dy[i];

				if (nr >= 0 && nc >= 0 && nr < n && nc < m && visit[nr][nc] == 0 && A[nr][nc] != 0) {
					visit[nr][nc] = 1;
					queue.push(nr);
					queue.push(nc);
				}
			}

		}
	}

}

class Queue {
	static int f, r, arr[];

	Queue(int c) {
		arr = new int[c];
		f = r = 0;
	}

	void push(int data) {
		arr[r] = data;
		r++;
	}

	int pop() {
		f++;
		return arr[f - 1];
	}

	boolean empty() {
		return f == r;
	}

	void reset() {
		r = f = 0;
	}
}
Leave a Comment