Untitled
unknown
plain_text
2 years ago
4.0 kB
3
Indexable
// Nuoc Bien package srv_NuocBien; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Iterator; import java.util.Scanner; public class Solution { static int N, M, ans, tc = 0; static int[][] map; static int[][] vis; static int count; static int[] dx = { 0, 1, 0, -1 }; static int[] dy = { 1, 0, -1, 0 }; static MyQueue myQx = new MyQueue(100000); static MyQueue myQy = new MyQueue(100000); public static void main(String[] args) { try { System.setIn(new FileInputStream("src/srv_NuocBien/input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner sc = new Scanner(System.in); while (true) { ans = 0; tc++; N = sc.nextInt(); M = sc.nextInt(); if (N == 0 && M == 0) { break; } map = new int[N][M]; vis = new int[N][M]; int max = 0; int min = 1001; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { map[i][j] = sc.nextInt(); if (map[i][j] > max) { max = map[i][j]; } if (map[0][j] < min) { min = map[0][j]; } if (map[N - 1][j] < min) { min = map[N - 1][j]; } if (map[i][0] < min) { min = map[i][0]; } if (map[i][M - 1] < min) { min = map[i][M - 1]; } } } int z = min; for (int nuoc = 1; nuoc < max; nuoc++) { count = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (map[i][j] != 0) { map[i][j] = map[i][j] - 1; } } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (map[i][j] != 0 && vis[i][j] == 0) { bfs(i, j); // count = count + z; count++; } } } if (count > 1 && check()) { ans = nuoc; break; } else { ans = -1; } reset(); } // in ra output System.out.print("Case #" + tc + ": "); if (ans == -1) { System.out.println("Island never splits."); } else { System.out.println("Island splits when ocean rises " + ans + " feet."); } // for (int i = 0; i < N; i++) { // for (int j = 0; j < M; j++) { // System.out.print(map[i][j] + " "); // } // System.out.println(); // } } } static boolean check() { int dem = 1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // if (map[0][j] != 0 && map[N - 1][j] != 0 && map[i][0] != 0 && map[i][M - 1] != 0) { // return false; // } // else if (map[0][j] == 0 && map[N - 1][j] == 0 && map[i][0] == 0 && map[i][M - 1] == 0) { // if (map[0 + dem][j] == 0 && map[N - 1 - dem][j] == 0 && map[i][0 + dem] == 0 // && map[i][M - 1 - dem] == 0) { // dem++; // } // // } // else if (map[0][j] == 0 || map[N - 1][j] == 0 || map[i][0] == 0 || map[i][M - 1] == 0) { return true; } } } return false; } static void reset() { vis = new int[N][M]; myQx.reset(); myQy.reset(); } static void bfs(int a, int b) { myQx.enQueue(a); myQy.enQueue(b); vis[a][b] = 1; while (!myQx.isEmpty()) { int x = myQx.deQueue(); int y = myQy.deQueue(); for (int i = 0; i < 4; i++) { int r = x + dx[i]; int c = y + dy[i]; if (r >= 0 && c >= 0 && r < N && c < M) { if (map[r][c] != 0 && vis[r][c] == 0) { myQx.enQueue(r); myQy.enQueue(c); vis[r][c] = 1; } } } } } } class MyQueue { private int front, rear, maxQueue; private int[] ArrayQueue; public MyQueue(int s) { maxQueue = s; ArrayQueue = new int[maxQueue]; front = rear = -1; } public boolean isEmpty() { if (front == rear) { return true; } return false; } public boolean isFull() { if (rear == maxQueue - 1) { return true; } return false; } public void reset() { front = rear = -1; } public void enQueue(int value) { rear++; ArrayQueue[rear] = value; } public int deQueue() { front++; return ArrayQueue[front]; } }
Editor is loading...