Nuoc Bien 100/100

 avatar
user_8149305
c_cpp
19 days ago
2.6 kB
2
Indexable
Never
// Dung BFS de tinh nuoc bien dang tu ngoai vao trong
//Dung BFSvung de tinh so vung sau khi nuoc bien dang
////Nuoc Bien

#include<iostream>
using namespace std;

int n, m;
int map[105][105];
int visited[105][105];
int maxN, minN;
int xQ[10000];
int yQ[10000];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int ans;

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

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

void BFS(int x, int y, int k) {
	int start = 0, last = 0;
	visited[x][y] = 1;
	xQ[last] = x;
	yQ[last++] = y;
	while (start != last) {
		int xC = xQ[start];
		int yC = yQ[start++];
		for (int i = 0; i < 4; i++) {
			int xN = xC + dx[i];
			int yN = yC + dy[i];
			if (checkBien(xN, yN) && map[xN][yN] <= k && visited[xN][yN] == 0) {
				visited[xN][yN] = 1;
				xQ[last] = xN;
				yQ[last++] = yN;
			}
		}
	}
}

void BFSvung(int x, int y) {
	int start = 0, last = 0;
	visited[x][y] = 1;
	xQ[last] = x;
	yQ[last++] = y;
	while (start != last) {
		int xC = xQ[start];
		int yC = yQ[start++];
		for (int i = 0; i < 4; i++) {
			int xN = xC + dx[i];
			int yN = yC + dy[i];
			if (checkBien(xN, yN) && visited[xN][yN] == 0) {
				visited[xN][yN] = 1;
				xQ[last] = xN;
				yQ[last++] = yN;
			}
		}
	}
}

void dangNuoc(int k) {
	for (int i = 0; i < n; i++) {
		if (map[i][0] <= k) {
			BFS(i, 0, k);
		}
		if (map[i][m - 1] <= k) {
			BFS(i, m - 1, k);
		}
	}
	for (int i = 1; i < m - 1; i++) {
		if (map[0][i] <= k) {
			BFS(0, i, k);
		}
		if (map[n - 1][i] <= k) {
			BFS(n - 1, i, k);
		}
	}
}

int demVung() {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visited[i][j] == 0) {
				BFSvung(i, j);
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	//FILE* f;
	//freopen_s(&f, "Text.txt", "r", stdin);
	int tc = 0;
	while (1) {
		tc++;
		cin >> n >> m;
		if (n == 0 && m == 0) {
			break;
		}
		else {
			maxN = 0; minN = 99999;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					cin >> map[i][j];
					matranke[i][j] = map[i][j];
					if (maxN < map[i][j]) maxN = map[i][j];
					if (minN > map[i][j] && map[i][j] != 0) {
						minN = map[i][j];
					}
				}
			}
			ans = 0;
			reset();
			for (int i = minN; i < maxN; i++) {
				dangNuoc(i);
				int cnt = demVung();
				if (cnt >= 2) {
					ans = i;
					break;
				}
				reset();
			}
			cout << "Case " << tc << " ";
			if (ans == 0) {
				cout << "Island never splits." << endl;
			}
			else {
				cout << "Island splits when ocean rises " << ans << " feet." << endl;
			}
		}
	}
	return 0;
}
Leave a Comment