Nuoc Bien 100/100
// 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