Untitled
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