Nuocbiensolquoc

 avatar
quoc14
c_cpp
21 days ago
2.9 kB
3
Indexable
Never
caidat
#include <iostream>

using namespace std;

int n, m;
int a[105][105];
int visit[105][105];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

bool inside(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= m) {
		return true;
	}
	return false;
}

void resetvisit() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visit[i][j] = 0;
		}
	}
}


void dfsnuocdang(int x_cur, int y_cur, int height) {
	visit[x_cur][y_cur] = 1;

	for (int i = 0; i < 4; i++) {
		int x_next = x_cur + dx[i];
		int y_next = y_cur + dy[i];
		if (inside(x_next, y_next)) {
			if (visit[x_next][y_next] == 0 && a[x_next][y_next] <= height) {
				dfsnuocdang(x_next, y_next, height);
			}
		}
	}
}


void dfsdemvung(int x_cur, int y_cur) {
	visit[x_cur][y_cur] = 1;

	for (int i = 0; i < 4; i++) {
		int x_next = x_cur + dx[i];
		int y_next = y_cur + dy[i];
		if (inside(x_next, y_next)) {
			if (visit[x_next][y_next] == 0) {
				dfsdemvung(x_next, y_next);
			}
		}
	}
}


bool check(int mid) {
	resetvisit();
	/*
	for (int j = 1; j <= m; j++) {
			if (a[1][j] <= mid && visit[1][j] == 0) {
				dfsnuocdang(1, j, mid);
			}
		}

	for (int i = 2; i <= n; i++) {
		if (a[i][m] <= mid && visit[i][m] == 0) {
			dfsnuocdang(i, m, mid);
		}
		if (a[i][1] <= mid && visit[i][1] == 0) {
			dfsnuocdang(i, 1, mid);
		}
	}


	for (int j = 2; j < m; j++) {
		if (a[n][j] <= mid && visit[1][j] == 0) {
			dfsnuocdang(n, j, mid);
		}
	}
	*/
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if ((i == 1 || i == n || j == 1 || j == m) && a[i][j] <= mid) {
				if (visit[i][j] == 0) {
				
					dfsnuocdang(i, j, mid);
				}
			}
		}
	}
	
	int vung = 0;

	

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (visit[i][j] == 0) {
				vung++;
				dfsdemvung(i, j);
			}
		}
	}
	//cout << vung << endl;
	if (vung >= 2) return true;

	return false;

	

}


void solve() {
	int t = 1;

	while (true) {
		
		cin >> n >> m;
		if (n == 0 && m == 0) {
			break;
		}
		
		int lo = 100000;
		int hi = -1;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
				if (a[i][j] > hi) {
					hi = a[i][j];
				}
				if (a[i][j] < lo) {
					lo = a[i][j];
				}
			}
		}

		
		
		int ans = 0;
		

		for (int mid = lo; mid <= hi; mid++) {
			if (check(mid)) {
				ans = mid;
				break;
			}
		}
		
		/*
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << visit[i][j] << " ";
			}
			cout << endl;
		}
		*/

		cout << "Case " << t << ": ";

		if (ans == 0) {
			cout << "Island never splits." << endl;
		}
		else {
			cout << "Island splits when ocean rises " << ans << " feet." << endl;
		}
		
		t++;
		
	}
}

int main() {
	freopen("Text.txt", "r", stdin);
	solve();

	return 0;
}
Leave a Comment