# Nuoc Bien 100/100

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;
}
```