Nuocbiensolquoc
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