Untitled

#include<iostream>
using namespace std;
#define maxx 1005
#define maxQ 100005
int n, m;
bool check = false;
int a[maxx][maxx];
int temp[maxx][maxx];
int visited[maxx][maxx];
int under[maxx][maxx];
int qx[maxx], qy[maxx];
int front, rear;
int height , X, Y;
int feet, minB;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

void init(){
	front = rear = -1;
}

bool isEmpty(){
	return front == rear;
}

void enQueue(int x, int y){
	rear = (rear + 1) % maxQ;
	qx[rear] = x;
	qy[rear] = y;
}

int deQueueX(){
	if(!isEmpty()){
		return qx[(front + 1)% maxQ];
	}
}

int deQueueY(){
	if(!isEmpty()){
		front = (front + 1)% maxQ;
		return qy[front];
	}
}

void reset(){
	for( int i =0; i < n; i++){
		for( int j = 0; j<m; j++){
			visited[i][j] = 0;
		}
	}
}

bool valid(int x, int y){
	return (x >= 0 && y >= 0 && x <n && y <m);
}

int bfsTran(int r, int c){
	init();
	under[r][c] = 1;
	int dt = 0;
	if(a[r][c] > 0) dt++;
	enQueue(r,c);
	while(!isEmpty()){
		int x  = deQueueX();
		int y = deQueueY();

		for(int i = 0; i<4; i++){
			int tx = x + dx[i];
			int ty = y + dy[i];

			if(valid(tx,ty) && under[tx][ty] == 0 && a[tx][ty] <= feet){
				
				if(a[tx][ty] > 0) dt++;
				under[tx][ty] = 1;
				enQueue(tx, ty);
			}
		}
	}

	return dt;
}

int dangNuoc(){
	int dtDaTran  = 0;
	
	for( int i =0; i < n; i++){
		for( int j =0; j < m; j++){
			under[i][j] = 0;
		}
	}

	for(int i =0; i< n; i++){
		if(a[i][0] <= feet && under[i][0] == 0){
			dtDaTran += bfsTran(i,0);
		}
		if(a[i][m-1] <= feet && under[i][m-1] == 0){
			dtDaTran += bfsTran(i,m-1);
		}
	}
	for(int i =1; i< m - 1; i++){
		if(a[0][i] <= feet && under[0][i] == 0){
			dtDaTran += bfsTran(0,i);
		}
		if(a[n-1][i] <= feet && under[n-1][i] == 0){
			dtDaTran += bfsTran(n-1,i);
		}
	}
	return dtDaTran;
}


int bfs(){
	int dtConLai = 1;
	init();
	reset();
	visited[X][Y] = 1;
	enQueue(X, Y);
	while(!isEmpty()){
		int x = deQueueX();
		int y = deQueueY();
		
		for( int i =0; i < 4; i++){
			int tx = x + dx[i];
			int ty = y + dy[i];

			if(valid(tx,ty) && visited[tx][ty] == 0 && under[tx][ty] == 0 && a[tx][ty] > 0 ){
				enQueue(tx,ty);
				visited[tx][ty] = 1;
				dtConLai++;

			}
		}
	}

	return dtConLai;
}

void solve(int dtBanDau){
	check = false;
	feet = 0;
	for( int i = minB ; i<= height; i++){
		int dtDaTran = 0;
		feet = i;
		dtDaTran = dangNuoc();

		int conlai = bfs();
		if(conlai != dtBanDau - dtDaTran){
			check = true;
			return;
		}
	}
}

void input(int t){
	cin >> n >> m;
	if(n == 0) return;
	int dtBanDau = 0;
	height = 0;
	minB = 1e9;
	for(int i =0; i < n; i++){
		for(int j =0; j< m; j++){
			cin >> a[i][j];
			if(a[i][j] > height) {
				height = a[i][j];
				X = i;
				Y = j;
			}

			if(a[i][j] < minB) {
				minB = a[i][j];
			}

			if(a[i][j] > 0) dtBanDau++;

			visited[i][j] = 0;
			under[i][j] = 0;
		}
	}

	cout << "Case " << t <<": ";
	solve(dtBanDau);

	if(feet == height)
		cout << "khong";
	else
		cout << feet << " feet";
		
	cout << endl;
}

int main(){
	freopen("input.txt", "r", stdin);
	n = 1;
	int t = 0;
	while(n != 0){
		t++;
		input(t);
	}
	return 0;
}