danggnuocsol

 avatar
quoc14
c_cpp
20 days ago
2.3 kB
4
Indexable
Never
*** my code ***
#include<iostream>
using namespace std;
#define MaxMap 110

int N, M;
int map[MaxMap][MaxMap];
int visit[MaxMap][MaxMap];

// queue
int const maxQ = 100000;
int qx[maxQ];
int qy[maxQ];
int front = -1;
int rear = -1;
bool isEmpty(){
	return front == -1;
}
void push(int x, int y){
	if (front == -1) front = 0;
	rear++;
	qx[rear] = x;
	qy[rear] = y;
}
void pop(){
	if (front >= rear) front = rear = -1;
	else front++;
}

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
void bfs(int x, int y){ // visit cac diem noi trong 1 vung
	front = rear = -1;
	visit[x][y] = 1;
	push(x,y);
	while (!isEmpty()){
		int x1 = qx[front];
		int y1 = qy[front];
		pop();
		for (int i = 0; i < 4; i++){
			int x2 = x1 + dx[i];
			int y2 = y1 + dy[i];
			if (x2>=0 && x2<N && y2>=0 && y2<M && visit[x2][y2]==0 && map[x2][y2]>0){
				visit[x2][y2] = 1;
				push(x2,y2);
			}
		}
	}
}

void resetVisit(){
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			visit[i][j] = 0;
		}
	}
}

int demVung(){
	int cnt = 0;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			if (map[i][j]>0 && visit[i][j]==0) {
				bfs(i,j);
				cnt++;
			}
		}
	}	
	return cnt;
}

void dangNuoc(){
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			if (map[i][j]!=0) map[i][j] -= 1;
		}
	}
}

bool checkNuocBien(){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if ( (i==0 || j==0 || i==N-1 || j==M-1) && map[i][j] == 0) return 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 ans = 0;
		int hightest = 0; 
		for (int i = 0; i < N; i++){
			for (int j = 0; j < M; j++){
				cin >> map[i][j];
				if (map[i][j] > hightest) hightest = map[i][j];
			}
		}
		bool split = false;
		// dang nuoc
		for (int i = 1; i <= hightest; i++){
			dangNuoc();
			resetVisit();
			int vung = demVung();
			if (vung > 1 && checkNuocBien()){
				split = true;
				ans = i;
				break;
			}
		}

		if(split == true) cout << "Case " << tc++ << ": Island splits when ocean rises " << ans << " feet." <<endl;
		else cout << "Case " << tc++ << ": Island never splits." <<endl;
	}

	return 0;
}
Leave a Comment