Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.0 kB
1
Indexable
Never
// 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];
	}

}