nuocbien

//nuoc bien
Nước biển
Trái đất nóng lên kéo theo mực nước biển dâng. Hòn đảo nhỏ Gonnasinka thuê bạn để dự báo trước hiểm họa này. Cho trước 1 lưới tọa độ thể hiện cao độ của đảo, hãy giúp họ tính toán xem nước biển dâng cao bao nhiêu thì hòn đảo sẽ bị chia cắt.

Input

Input gồm nhiều bộ test, mỗi bộ test bao gồm:

Dòng đầu ghi 2 số n, m là chiều dài và chiều rộng.

Sau đó là n dòng, mỗi dòng gồm m số, mỗi số cho biết độ cao của ô đó, giá trị 0 chỉ mực nước biển. Những ô giá trị 0 dọc theo đường viền và những ô số 0 liền kề những ô này chỉ mặt biển. Những ô có giá trị 0 còn lại (được bao bọc bởi các số > 0) là đất liền bên trong đảo nhưng có độ cao ngang mặt nước biển. Hòn đảo lúc đầu chưa bị chia cắt. Số n và m không lớn hơn 100 và độ cao không lớn hơn 1000.

Dòng cuối cùng của input chứa 2 số 0

Output

Với mỗi bộ test, in ra:

Case n: Island splits when ocean raises f feet. (Đảo bị chia khi nước biển dâng cao f feet)

Hoặc

Case n: Island never splits. (Đảo không bao giờ bị chia cắt)

Example

Input:

5 5

3 4 3 0 0

3 5 5 4 3

2 5 4 4 3

1 3 0 0 0

1 2 1 0 0

5 5

5 5 5 5 7

4 1 1 1 4

4 1 2 1 3

7 1 0 0 4

7 3 4 4 4

0 0

Output:

Case 1: Island never splits.

Case 2: Island splits when ocean rises 3 feet.
///==================================================================

#include <iostream>
using namespace std;

int T,N, M;
int Map[102][102];
int visit[102][102];
int ans;
int qu[40000];
int rear, front;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int maxH;

void enqu(int a){
	rear++;
	qu[rear] =a;
}

int dequ(){
	front++;
	return qu[front];
}

int highest;
void BFS(int x, int y, int h){
	rear = front = -1;
	enqu(x);
	enqu(y);
	visit[x][y] = 1;
	while(rear > front){
		int nowx = dequ();
		int nowy = dequ();
		for(int i = 0; i<4; i++){
			int nx = nowx+dx[i];
			int ny = nowy+dy[i];
			if (nx >= 0 && nx < N + 2 && ny >= 0 && ny < M + 2 && visit[nx][ny] == 0 ){
				if (Map[nx][ny] <= h){
					enqu(nx);
					enqu(ny);
					visit[nx][ny] = 1;
				}
			}
		}
	}
}


int Find(int from, int to){
	for(int n = from; n<to; n++){

		for(int i = 0; i<N+2; i++){
			for(int j = 0; j<M+2; j++){
				visit[i][j] = 0;
			}
		}

		int h = (from + to)/2;
		BFS(0, 0, n);
		int flag = 0;
		for(int i = 1; i<=N; i++){
			for(int j = 1; j<=M; j++){
				if(visit[i][j] == 0 && flag == 0){
					BFS(i, j, 1000);
					flag ++;
				}
				else if (visit[i][j] == 0 && flag > 0){
					flag++;
					break;
				}
			}
			if (flag ==2) 
				break;
		}
		if (flag == 2)
			return n;
	}
	return -1;
}


int main(){

	//freopen("input.txt", "r", stdin);
	cin >> N >> M;
	for( int tc = 1; N!=0 && M!= 0; tc++){

		for(int i = 0; i<N+2; i++){
			for(int j = 0; j<M+2; j++){
				Map[i][j] = 0;
				visit[i][j] = 0;
			}
		}
		maxH = 0;
		for(int i = 0; i<N; i++){
			for(int j = 0; j<M; j++){
				cin >> Map[i+1][j+1];
				if (Map[i+1][j+1] > maxH)
					maxH = Map[i+1][j+1];
			}
		}


		int ans  = Find(0, maxH+1);
		if (ans == -1)
			cout << "Case " << tc << ": Island never splits."<< endl;
		else
			cout << "Case " << tc << ": Island splits when ocean rises "<< ans <<" feet."<< endl;
		cin >> N >> M;
	}
	return 0;
}