Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.7 kB
5
Indexable
Never
#include <iostream>
using namespace std;
class Queue
{
private:
	int front, rear;
	int Data[100000000];
public:
	Queue();
	void reset();
	void enQueue(int value);
	int deQueue();
	bool isEmpty();
};
Queue::Queue(){
	front=rear=-1;
}
void Queue::reset(){
	front=rear=-1;
}
void Queue::enQueue(int value){
	Data[++rear]=value;
}
int Queue::deQueue(){
	return Data[++front];
}
bool Queue::isEmpty(){
	return front==rear;
}
Queue rQueue, cQueue;
int N, M, Map[100][100], visit[100][100];
int dx[]={0,0,-1,1},
	dy[]={-1,1,0,0};
void BFS(int value){
	for (int i=0; i<N; i++){
		for (int j=0; j<M; j++){
			visit[i][j]=false;
		}
	}
	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]<=value && visit[i][j]==false)
			{
				rQueue.reset();
				cQueue.reset();
				rQueue.enQueue(i);
				cQueue.enQueue(j);
				visit[i][j]=true;
				while (rQueue.isEmpty()==false){
					int cr=rQueue.deQueue();
					int cc=cQueue.deQueue();
					for (int idx=0; idx<4; idx++){
						int nr=cr+dx[idx];
						int nc=cc+dy[idx];
						if (nr>=0 && nr<N && nc>=0 && nc<M &&
							Map[nr][nc]<=Map[cr][cc] && visit[nr][nc]==false)
						{
							rQueue.enQueue(nr);
							cQueue.enQueue(nc);
							visit[nr][nc]=true;
						}
					}
				}
			}
		}
	}
}
bool Split(){
	int vung=0;
	for (int i=0; i<N; i++){
		for (int j=0; j<M; j++){
			if (visit[i][j]==false){
				vung++;
				if (vung==2)
					return true;
				rQueue.reset();
				cQueue.reset();
				rQueue.enQueue(i);
				cQueue.enQueue(j);
				visit[i][j]=true;
				while (rQueue.isEmpty()==false){
					int cr=rQueue.deQueue();
					int cc=cQueue.deQueue();
					for (int idx=0; idx<4; idx++){
						int nr=cr+dx[idx];
						int nc=cc+dy[idx];
						if (nr>=0 && nr<N && nc>=0 && nc<M
							&& visit[nr][nc]==false)
						{
							rQueue.enQueue(nr);
							cQueue.enQueue(nc);
							visit[nr][nc]=true;
						}
					}
				}
			}
		}
	}
	return false;
}

int main(){
	freopen("input.txt", "r", stdin);
	int tc=1;
	while(1){
		cin>>N>>M;
		if (N==0 && M==0)
			break;
		int level=0, Max=0;
		for (int i=0; i<N; i++){
			for (int j=0; j<M; j++){
				cin>>Map[i][j];
				if (Map[i][j]>Max)
					Max=Map[i][j];
			}
		}
		while(1){
			if (level==Max){
				cout<<"Case "<<tc<<": Island never splits."<<endl;
				break;
			}
			BFS(level);
			//Neu hon dao bi chia cat
			if (Split()==true){
				cout<<"Case "<<tc<<": Island splits when ocean raises "<< level <<" feet."<<endl;
				break;
			}
			level++;
		}
		tc++;
	}

	return 0;
}
Leave a Comment