Untitled
unknown
plain_text
22 days ago
3.2 kB
1
Indexable
Never
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, m, h, max, min, visit[][], A[][]; // static int A[][] = 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; A = new int[n][m]; 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(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 j = 0; j < m; j++) { if (i == 0 || i == n - 1 || j == 0 || j == m - 1) { if (A[i][j] == k) { 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 queue.reset(); queue.push(x); queue.push(y); visit = new int[n][m]; visit[x][y] = 1; A[x][y] = 0; 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