Untitled

mail@pastecode.io avatar
unknown
plain_text
10 months ago
4.8 kB
2
Indexable
Never
import java.util.Scanner;

/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
	static int[][] a;
	static int[][] visit;
	static Node[] queue = new Node[10005];
	static int start, end;
	static int[] dx = {0,0, -1, 1};
	static int[] dy = {-1,1,0,0};
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t = 1;
		while (true) {
			int row = sc.nextInt();
			int col = sc.nextInt();
			a = new int[row][col];
			if (row == 0 && col == 0) {
				break;
			}
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					a[i][j] = sc.nextInt();
				}
			}
			int feet = 1;
			int lienthong = 0;
			while (true) {
				
				visit = new int[row][col];
				//duyet hang thu 1
				for (int i = 0; i < col; i++) {
					if (a[0][i] <= feet && visit[0][i] == 0) {
						start = end = -1;
						push(new Node(0,i));
						visit[0][i] = 1;
						a[0][i]= 0;
						while (start < end) {
							Node node = pop();
							for (int j = 0; j < 4; j++) {
								int x = node.r + dx[j];
								int y = node.c + dy[j];
								if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
									a[x][y] = 0;
									push(new Node(x,y));
									visit[x][y] = 1;
								}
							}
						}
					}
				}
				
				//duyet hang cuoi
				for (int i = 0; i < col; i++) {
					if (a[row-1][i] <= feet && visit[row-1][i] == 0) {
						start = end = -1;
						push(new Node(row-1,i));
						visit[row-1][i] = 1;
						a[row-1][i] = 0;
						while (start < end) {
							Node node = pop();
							for (int j = 0; j < 4; j++) {
								int x = node.r + dx[j];
								int y = node.c + dy[j];
								if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
									a[x][y] = 0;
									 
									push(new Node(x,y));
									visit[x][y] = 1;
								}
							}
						}
					}
				}
				
				//duyet cot dau
				for (int i = 1; i < row - 1; i++) {
					if (a[i][0] <= feet && visit[i][0] == 0) {
						start = end = -1;
						push(new Node(i,0));
						visit[i][0] = 1;
						a[i][0] = 0;
						while (start < end) {
							Node node = pop();
							for (int j = 0; j < 4; j++) {
								int x = node.r + dx[j];
								int y = node.c + dy[j];
								if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
									a[x][y] = 0;
									 
									push(new Node(x,y));
									visit[x][y] = 1;
								}
							}
						}
					}
				}
				//duyet cot cuoi
				for (int i = 1; i < row - 1; i++) {
					if (a[i][col-1] <= feet && visit[i][col-1] == 0) {
						start = end = -1;
						push(new Node(i,col-1));
						visit[i][col-1] = 1;
						a[i][col-1] = 0;
						while (start < end) {
							Node node = pop();
							for (int j = 0; j < 4; j++) {
								int x = node.r + dx[j];
								int y = node.c + dy[j];
								if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
									a[x][y] = 0;
									 
									push(new Node(x,y));
									visit[x][y] = 1;
								}
							}
						}
					}
				}
				
				//duyet toan bo ma tran dem thanhf phan lien thong
				//neu khong co thanh phan lien thong ( toan bo ma tran la 0) ghi nhan ket qua
				//Neu thanh phan lien thong > 1 -> dao bi chia cat
				//Thanh phan lien thong = 1 lai tang feet len de xet tiep
				visit = new int[row][col];
				lienthong = 0;
				for (int i = 0; i < row; i++) {
					for (int j = 0; j < col; j++) {
						if (a[i][j] != 0 && visit[i][j] == 0) {
							
							lienthong++;
							start = end = -1;
							push(new Node(i,j));
							visit[i][j] = 1;
							while (start < end) {
								Node node = pop();
								for (int k = 0; k < 4; k++) {
									int x = node.r + dx[k];
									int y = node.c + dy[k];
									if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] > 0 && visit[x][y] == 0) {
										
										 
										push(new Node(x,y));
										visit[x][y] = 1;
									}
								}
							}
						}
					}
				}
				if (lienthong == 0 || lienthong > 1) {
					break;
				}
				
				feet++;
			}
			System.out.print("Case " + t + ": ");
			if (lienthong == 0) {
				System.out.println("Island never splits.");
			} else {
				System.out.println("Island splits when ocean rises "+  feet +  " feet.");
			}
			t++;
		}
	}
	
	private static void push(Node node) {
		end++;
		queue[end] = node;
	}
	
	private static Node pop() {
		start++;
		return queue[start];
	}
	static class Node {
		int r, c;
		public Node (int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
}
Leave a Comment