dangnuocsol1

 avatar
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