Untitled
unknown
c_cpp
2 years ago
2.7 kB
6
Indexable
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int n, m; int arr[101][101]; bool vis[101][101]; bool cheese[101][101]; int diffx[4] = {0,0,1,-1}; int diffy[4] = {1,-1,0,0}; int cntCheese = 0; deque<pii> deq; deque<pii> che; int bfs1(){ while(!che.empty()){ pii cur = che.front(); che.pop_front(); int y = cur.first; int x = cur.second; for(int i = 0;i<4;i++){ int ny = y + diffy[i]; int nx = x + diffx[i]; if(0>ny || n<=ny || 0>nx || m <= nx) continue; if(arr[ny][nx] ==1 && !vis[ny][nx]){ // cheese exist vis[ny][nx] = true; deq.push_back({ny,nx}); // check by bfs2 }else if(arr[ny][nx]==0){ arr[ny][nx] = 2; // already check che.push_back({ny,nx}); } } } return deq.size(); } int T; int bfs2(){ deque<pii> rem; while(!deq.empty()){ for(int i = 0;i<deq.size();i++){ pii cur = deq.front(); deq.pop_front(); // pop int y = cur.first; int x = cur.second; int cnt = 0; for(int i = 0;i<4;i++){ int ny = y + diffy[i]; int nx = x + diffx[i]; if(0>nx || n <= nx || 0>ny || n <= ny) continue; if(arr[ny][nx]==2){ cnt++; } } if(cnt>=2){ che.push_back({y,x}); }else{ rem.push_back({y,x}); } } } for(int i = 0;i<che.size();i++){ arr[che[i].first][che[i].second] = 2; cntCheese--; } while(!rem.empty()){ deq.push_back(rem.front()); rem.pop_front(); } return che.size(); } void Print(){ for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ cout << arr[i][j] << " "; } cout << '\n'; } cout << '\n'; } bool chk(){ for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ if(arr[i][j]!=2){ return false; } } } return true; } int main(void){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n >> m; for(int i =0;i<n;i++){ for(int j = 0;j<m;j++){ cin >> arr[i][j]; if(arr[i][j]){ cntCheese++; } } } che.push_back({0,0}); while(1) // 시작할 곳을 탐색 { // if(chk()) break; if(cntCheese<=0) { break; } // Print(); bfs1(); bfs2(); // 녹이기 T++; } // Print(); cout << T <<'\n'; }
Editor is loading...