/* * Seems to work, but only if stack size is bigger than default (e.g., * -Xss1m) */ import java.util.*; class Node implements Comparable { public int row,col; public ArrayList nbr; public int ht; public Node(int r, int c, int h) { row = r; col = c; ht = h; nbr = new ArrayList(); } public void add(Node n) { nbr.add(n); } public void del(int r, int c) { boolean ok = false; for (Node nd: nbr) { if (nd.row == r && nd.col == c) { nbr.remove(nd); break; } } } public int compareTo(Node other) { if (this.ht < other.ht) return -1; else if (this.ht > other.ht) return 1; else return 0; } } class Pair { int i,j; public Pair(int x, int y) { i = x; j = y; } } public class Flood { public static int n, m, caseNum; public static int[][] alt; public static Scanner in; public static Node island[][]; public static Node sorted[]; public static boolean visited[][]; public static boolean outer[][]; public static int numVisited; public static int nonZero; public static void main(String[] args) { caseNum = 0; in = new Scanner(System.in); while (true) { n = in.nextInt(); m = in.nextInt(); if (n == 0 && m == 0) { break; } caseNum++; alt = new int[n][m]; outer = new boolean[n][m]; for (int i = 0; i < n; i++) Arrays.fill(outer[i],false); nonZero = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { alt[i][j] = in.nextInt(); if (alt[i][j] > 0) nonZero++; if (i == 0 || i == n-1 || j == 0 || j == m-1) outer[i][j] = true; } } boolean change = true; while (change) { change = false; for (int i = 1; i < n-1; i++) { for (int j = 1; j < m-1; j++) { if (outer[i][j]) continue; if ((alt[i-1][j] == 0 && outer[i-1][j]) || (alt[i+1][j] == 0 && outer[i+1][j]) || (alt[i][j-1] == 0 && outer[i][j-1]) || (alt[i][j+1] == 0 && outer[i][j+1])) { outer[i][j] = true; change = true; } } } } int ans = solve(); if (ans == 0) { System.out.println("Case " + caseNum + ": Island never splits."); } else { System.out.println("Case " + caseNum + ": Island splits when ocean" + " rises " + ans + " feet."); } } } public static int solve() { island = new Node[n][m]; sorted = new Node[nonZero]; // non-zero nodes sorted by height int k = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { island[i][j] = new Node(i,j,alt[i][j]); if (alt[i][j] > 0) sorted[k++] = island[i][j]; } } Arrays.sort(sorted); int size = 0; int startRow = -1, startCol = -1; // place to begin dfs for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (alt[i][j] == 0 && outer[i][j]) continue; size++; if (startRow < 0) { startRow = i; startCol = j; } if (i+1 < n && (alt[i+1][j] > 0 || !outer[i+1][j])) { island[i][j].add(island[i+1][j]); } if (j+1 < m && (alt[i][j+1] > 0 || !outer[i][j+1])) { island[i][j].add(island[i][j+1]); } if (i > 0 && (alt[i-1][j] > 0 || !outer[i-1][j])) { island[i][j].add(island[i-1][j]); } if (j > 0 && (alt[i][j-1] > 0 || !outer[i][j-1])) { island[i][j].add(island[i][j-1]); } } } int i = 0; // next node in sorted array int ht = 0; // most recent previous height int prevHt = -1; while (true) { visited = new boolean[n][m]; for (int l = 0; l < n; l++) Arrays.fill(visited[l],false); numVisited = 0; dfs(startRow,startCol); if (numVisited < size) { return prevHt; } int count = 0; // number of newly-submerged cells while (i < nonZero && sorted[i].ht == ht) { int r = sorted[i].row; int c = sorted[i].col; if (outer[r][c]) { count++; if (r-1 >= 0) { island[r-1][c].del(r,c); } if (r+1 < n) { island[r+1][c].del(r,c); } if (c-1 >= 0) { island[r][c-1].del(r,c); } if (c+1 < m) { island[r][c+1].del(r,c); } } i++; if (r == startRow && c == startCol && i < nonZero) { startRow = sorted[i].row; startCol = sorted[i].col; } } boolean change = true; while (change) { change = false; for (int x = 1; x < n-1; x++) { for (int y = 1; y < m-1; y++) { if (!outer[x][y] && ((alt[x-1][y] <= ht && outer[x-1][y]) || (alt[x+1][y] <= ht && outer[x+1][y]) || (alt[x][y-1] <= ht && outer[x][y-1]) || (alt[x][y+1] <= ht && outer[x][y+1]))) { outer[x][y] = true; if (alt[x][y] <= ht) { count++; island[x-1][y].del(x,y); island[x+1][y].del(x,y); island[x][y-1].del(x,y); island[x][y+1].del(x,y); } change = true; } } } } if (i < nonZero) { prevHt = ht; ht = sorted[i].ht; size -= count; } else return 0; } } public static void dfs(int r, int c) { Node nd = island[r][c]; visited[r][c] = true; numVisited++; for (Node nb: nd.nbr) { if (!visited[nb.row][nb.col]) dfs(nb.row,nb.col); } } }