Untitled

 avatar
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...