Untitled

Nuoc bien dang roi
#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
using namespace std;
#define MAX_N 100

int map[MAX_N][MAX_N];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

int N, M;


int Q[MAX_N * MAX_N];
int front, rear;


bool under[MAX_N][MAX_N];

int visited[MAX_N][MAX_N];
int coveredCnt;

void BFS2(int r, int c, int level)
{
	front = rear = 0;
	Q[0] = r * MAX_N + c;
	under[r][c] = true;
	if (map[r][c])
		coveredCnt++;
	int nextR, nextC;
	while (front <= rear) {
		r = Q[front] / MAX_N;
		c = Q[front++] % MAX_N;
		for (int d = 0; d < 4; d++) {
			nextR = r + dy[d];
			nextC = c + dx[d];
			if (nextR < 0 || nextR == N || nextC < 0 || nextC == M || under[nextR][nextC] || map[nextR][nextC] > level)
				continue;
			if (map[nextR][nextC]) coveredCnt++;
			under[nextR][nextC] = true;
			Q[++rear] = nextR * MAX_N + nextC;
		}
	}
}


void raiseWater(int level)
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			under[i][j] = false;
	int ret = 0;
	for (int i = 0; i < N; i++) {
		if (map[i][0] <= level && !under[i][0])
			BFS2(i, 0, level);
		if (map[i][M - 1] <= level && !under[i][M - 1])
			BFS2(i, M - 1, level);
	}
	for (int i = 1; i < M - 1; i++) {
		if (map[0][i] <= level && !under[0][i])
			BFS2(0, i, level);
		if (map[N - 1][i] <= level && !under[N - 1][i])
			BFS2(N - 1, i, level);
	}
}

int countArea(int r, int c)
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			visited[i][j] = false;
	front = rear = 0;
	Q[0] = r * MAX_N + c;
	visited[r][c] = 1;
	int ret = 1;
	int nextR, nextC;
	while (front <= rear) {
		r = Q[front] / MAX_N;
		c = Q[front++] % MAX_N;
		for (int d = 0; d < 4; d++) {
			nextR = r + dy[d];
			nextC = c + dx[d];
			if (nextR < 0 || nextR == N || nextC < 0 || nextC == M || visited[nextR][nextC])
				continue;
			if (!under[nextR][nextC] && map[nextR][nextC]) {
				visited[nextR][nextC] = 1;
				Q[++rear] = nextR * MAX_N + nextC;
				ret++;
			}

		}
	}
	return ret;
}

int main()
{
	freopen("input.txt", "r", stdin);
	int tc = 0;
	int lowest, highest;
	int oceanArea, remainLand;
	int initLand;
	while (true) {
		scanf("%d%d", &N, &M);
		if (N == 0 && M == 0)
			break;
		tc++;
		lowest = 1000000;
		highest = 0;
		initLand = 0;
		int highestR, highestC;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				scanf("%d", &map[i][j]);
				if (map[i][j] > highest) {
					highestR = i;
					highestC = j;
					highest = map[i][j];
				}
				if (map[i][j] && map[i][j] < lowest) lowest = map[i][j];
				if (map[i][j])
					initLand++;
			}
		}
		int m;
		for (m = lowest; m < highest; m++) {
			coveredCnt = 0;
			raiseWater(m);
			remainLand = countArea(highestR, highestC);
			if (remainLand != initLand - coveredCnt)
				break;
		}
		if (m == highest)
			printf("Case %d: Island never splits.\n", tc);
		else
			printf("Case %d: Island splits when ocean rises %d feet.\n", tc, m);

	}
	return 0;
}