Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.2 kB
3
Indexable
#include<iostream>
using namespace std;

int T, hang, cot;
int arr[105][105], visit[105][105];
int rs, flag, maxx;
int dx[4]= {-1,0,1,0};
int dy[4]= {0,1,0,-1};

void nhap(){
	for(int i = 0; i <= hang +1; i ++) {
		arr[i][0] = 0;
		arr[i][cot+1] = 0;
	}
	for(int i = 0; i <= cot +1; i ++) {
		arr[0][i] = 0;
		arr[hang+1][i] = 0;
	}
	for(int i = 1; i <= hang; i ++) {
		for(int j = 1; j <= cot; j ++) {
			cin >> arr[i][j];
			if(arr[i][j] > maxx) maxx = arr[i][j];
		}
	}
}

void reset(){
	for(int i = 0; i <= hang+1; i ++) {
		for(int j = 0; j <= cot+1; j ++) {
			visit[i][j] = 0;
		}
	}
}

bool cdk(int x, int y) {
	if(x >= 0 && x <= hang+1 && y >=0 && y <= cot+1) return true;
	return false;
}
bool cdk1(int x, int y) {
	if(x > 0 && x < hang+1 && y > 0 && y < cot+1) return true;
	return false;
}
void dfs(int x, int y, int k) {
	visit[x][y] = 1;
	for(int i = 0; i < 4; i ++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(cdk(xx,yy) && !visit[xx][yy] && arr[xx][yy] <= k) {
			visit[xx][yy] = 1;
			dfs(xx,yy,k);
		}
	}
}

void dequy(int x, int y){
	visit[x][y] = 1;
	for(int i = 0; i < 4; i ++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(cdk1(xx,yy) && !visit[xx][yy]) {
			visit[xx][yy] = 1;
			dequy(xx,yy);
		}
	}
}

bool check() {
	for(int i = 1; i < hang + 1; i ++) {
		for(int j = 1; j < cot + 1; j ++) {
			if(!visit[i][j]) return false;
		}
	}
	return true;
}

int main() {
	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	int t = 1;
	while(t++){
		cin >> hang >> cot;
		if(hang == 0 && cot == 0) break;
		maxx = 0;
		nhap();
		int k = 0;
		rs = -1;
		while(true) {
			reset();
			dfs(0,0,k);
			for(int i = 1; i < hang +1; i ++) {
				for(int j = 1; j < cot + 1; j ++) {
					if(arr[i][j] > k) {
						dequy(i,j);
						i = 1000; j = 1000;
					}
				}
			}
			if(check()) k ++;
			else {
				rs = k;
				break;
			}
			if(k > maxx) break;
		}
		cout << "Case " << t - 1<< ": ";
		if(rs == -1) cout << "Island never splits." << endl;
		else cout << "Island splits when ocean rises " << rs << " feet." << endl;
	}
	return 0;
}