Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.3 kB
1
Indexable
Never
#include<iostream>

using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
int a[101][101];
int vs[101][101];
int qx[5000000];
int qy[5000000];
int f=-1;
int r=-1;
int n,m; 
void push( int x, int y)
{
	r++;
	qx[r]=x;
	qy[r]=y;
}

void pop(int &x, int &y)
{
	f++;
	x=qx[f];
	y=qy[f];
}

bool checkbien(int x, int y)
{
	if(x<0||x>=n||y<0||y>=m) return false;
	return true;
}

int BFSngap(int x, int y, int z)
{
	int t=1;
	push(x,y);
	vs[x][y]=1;
	while(r!=f){
		pop(x,y);
		for(int i=0;i<4;i++){
			int x1=x+dx[i];
			int y1=y+dy[i];
			if(checkbien(x1,y1)){
				if(a[x1][y1]<=z && vs[x1][y1]==0){
					t++;
					push(x1,y1);
					vs[x1][y1]=1;
				}
			}
		}
	}
	return t;
}

int BFS(int x, int y, int z)
{
	int t1=1;
	push(x,y);
	vs[x][y]=1;
	while(r!=f){
		pop(x,y);
		for(int i=0;i<4;i++){
			int x1=x+dx[i];
			int y1=y+dy[i];
			if(checkbien(x1,y1)){
				if(vs[x1][y1]==0){
					t1++;
					push(x1,y1);
					vs[x1][y1]=1;
				}
			}
		}
	}
	return t1;
}
int main()
{
	freopen("input.txt", "r",stdin);
	while(1){
		cin >> n >>m;
		if(n==0&& m==0) break;
		int tc=1;
		int max=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>> a[i][j];
				if(a[i][j]>max) max=a[i][j];
			}
		}
		int min=99;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				vs[i][j]=0;
				if(i==0||i==n-1||j==0||j==m-1){
					if(min>a[i][j]) min=a[i][j];
				}
			}
		}

		bool check=true;
		int k;
		for(k=min;k<=max;k++){
			int tong=0;
			int tong1=0, d=0;
			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){
						if(a[i][j]<=k && vs[i][j]==0)
						tong+=BFSngap(i,j,k);
					}
				}
			}
			for(int i=0; i<n;i++){
				for(int j=0;j<m;j++){
					if(a[i][j]>k && vs[i][j]==0){
						d++;
						if(d==1){
							tong1=BFS(i,j,k);
						}
					}
				}
			}
			int ans=tong+tong1;
			//cout <<k<< " "<<tong <<" "<<tong1<< " " <<ans<< endl;
			if(ans<n*m){
				check=false;
				break;
			}
			for(int i=0;i<n;i++){
				for(int j=0;j<m;j++){
				vs[i][j]=0;
				}
			}
		}


		if(check) cout<< "Island never splits." << endl;
		else cout << "Island splits when ocean rises " << k <<" feet." << endl;
		tc++;
	}
	return 0;
}