dangnuocsol1
quoc14
c_cpp
22 days ago
1.9 kB
2
Indexable
Never
caidat
#include <iostream> using namespace std; int map[105][105]; int vis[105][105]; int N,M; int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; void DFS_water(int r, int c, int water){ vis[r][c] = 1; for (int k = 0; k < 4; k++) { int x = r + dx[k]; int y = c + dy[k]; if (x <0 || x >= N || y<0 ||y >=M || vis[x][y] !=0) continue; if (map[x][y] <= water) { vis[x][y] = 1; DFS_water(x,y,water); } } } void DFS_island(int r, int c) { vis[r][c] =1; for (int k = 0; k < 4; k++) { int x = r + dx[k]; int y = c + dy[k]; if (x <0 || x >= N || y<0 ||y >=M || vis[x][y] !=0) continue; DFS_island(x,y); } } void clear_vis(){ for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { vis[i][j] = 0; } } } int main(){ //freopen("input.txt","r",stdin); cin>>N>>M; int tc =0; while (N!=0 && M!=0) { tc++; int low = 1000, high = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin>>map[i][j]; if(map[i][j] < low) low = map[i][j]; if(map[i][j] > high) high = map[i][j]; } } int ans =-1; for (int water = low; water <= high; water++) { clear_vis(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if ((i==0 || i == N-1 || j == 0 || j == M-1) && map[i][j] <= water) { if (vis[i][j] == 0) { DFS_water(i,j,water); } } } } int dem =0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (vis[i][j] ==0) { DFS_island(i,j); dem++; } } } if (dem > 1) { ans = water; break; } } if (ans == -1) { cout<<"Case "<<tc<<": Island never splits."<<endl; } else { cout<<"Case "<<tc<<": Island splits when ocean rises "<<ans<<" feet."<<endl; } cin>>N>>M; } return 0; }
Leave a Comment