danggnuocsol
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