Untitled

 avatar
duybe2K
plain_text
7 months ago
3.7 kB
1
Indexable
Never
package OT;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

class Position {
	int x, y;

	public Position(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class NB {
	static int n, m, arr[][], visit[][], startX, startY, front, rear, Min;

	static int spinX[] = { 1, -1, 0, 0 };
	static int spinY[] = { 0, 0, 1, -1 };
	static Position data[] = new Position[1000005];

	static void reset() {
		front = rear = -1;
	}

	static Position pop() {
		return data[++rear];
	}

	static void push(Position val) {
		data[++front] = val;
	}

	static boolean isE() {
		return front == rear;
	}

	static boolean checkbien(int x, int y) {
		if (x >= 0 && x < n && y >= 0 && y < m) {
			return true;
		}
		return false;
	}

	private static void bfs(int min) {
		resetV();
		reset();
		Position position = null;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] <= min) {
					if (i == 0) {
						position = new Position(i, j);
						push(position);
						visit[i][j] = 1;
					}
					if (j == 0) {
						position = new Position(i, j);
						push(position);
						visit[i][j] = 1;
					}
					if (j == m - 1) {
						position = new Position(i, j);
						push(position);
						visit[i][j] = 1;
					}
					if (i == n - 1) {
						position = new Position(i, j);
						push(position);
						visit[i][j] = 1;
					}
				}

			}
		}

		while (!isE()) {
			position = pop();
			int cr = position.x;
			int cc = position.y;
			for (int i = 0; i < 4; i++) {
				int nr = cr + spinX[i];
				int nc = cc + spinY[i];
				if (checkbien(nr, nc) && visit[nr][nc] == 0 && arr[nr][nc] <= min) {
					position = new Position(nr, nc);
					push(position);
					arr[nr][nc] = 0;
					visit[nr][nc] = 1;
				}
			}
		}
	}

	static void bfschiavung(int r, int c) {
		Position position = new Position(r, c);
		push(position);
		visit[r][c] = 1;
		while (!isE()) {
			position = pop();
			int cr = position.x;
			int cc = position.y;
			for (int i = 0; i < 4; i++) {
				int nr = cr + spinX[i];
				int nc = cc + spinY[i];
				if (checkbien(nr, nc) && visit[nr][nc] == 0 && arr[nr][nc] != 0) {
					position = new Position(nr, nc);
					push(position);
					visit[nr][nc] = 1;
				}
			}
		}
	}

	static void resetV() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visit[i][j] = 0;
			}
		}
	}

	static int tinhvum() {
		int count = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] != 0 && visit[i][j] == 0) {
					bfschiavung(i, j);
					count++;
				}
			}
		}
		return count;
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Input.txt"));
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		int tc = 1;
		while (n != 0 && m != 0) {

			arr = new int[n][m];
			visit = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					arr[i][j] = scanner.nextInt();
				}
			}
			int max = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (arr[i][j] > max) {
						max = arr[i][j];
					}
				}
			}
			int count = tinhvum();
			int ans = 0;
			for (int i = 0; i < max; i++) {
				bfs(i);
				if (tinhvum() > count) {
					ans = i;
					break;
				}
			}
			System.out.println("Case "+tc+ ": "+(ans!=0? "Island splits when ocean rises "+ ans+" feet.": "Island never splits."));
			tc++;
			n = scanner.nextInt();
			m = scanner.nextInt();
		}
	}
}
Leave a Comment