baekjun 7576. 토마토

 bfs 연습문제

/*6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1*/
 
#include <iostream>
#include <algorithm>
#include <list>
#include <cstring>
using namespace std;
 
int M, N;
int box[1001][1001];
int visitedList[1001][1001];
 
/*
0 : raw tomato
-1 : empty
1 : cooked tomato
*/
int main(){
    int rawCnt = 0;
    memset(visitedList, -1, sizeof(visitedList));
    list<pair<int, int>> que;
    cin >> M >> N;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++){
            cin >> box[i][j];
            if(box[i][j] == 1){
                que.push_front(make_pair(i, j));
                visitedList[i][j] = 1;
            } else if(box[i][j] == 0){
                visitedList[i][j] = 0;
                rawCnt++;
            } else {
                visitedList[i][j] = -1;
            }
        }
 
    int day = 0;
    while(rawCnt){
 
        day++;
        list<pair<int, int>> buf;
        if(que.empty()){
            cout << -1;
            return 0;
        }
        while(!que.empty()){
            pair<int, int> ret = que.back();
            int i = ret.first, j=ret.second;
            que.pop_back();
 
            if(i-1 > 0){
                if(visitedList[i-1][j] == 0){
                    rawCnt--;
                    //cout << "rawCnt : " << rawCnt << endl;
                    buf.push_back(make_pair(i-1, j));
                    visitedList[i-1][j] = 1;
                }
            }
            if(i + 1 <= N){
                if(visitedList[i+1][j] == 0){
                    rawCnt--;
                    //cout << "rawCnt : " << rawCnt << endl;
                    buf.push_back(make_pair(i+1, j));
                    visitedList[i+1][j] = 1;
                }
            }
            if(j-1 > 0){
                if(visitedList[i][j-1] == 0){
                    rawCnt--;
                    //cout << "rawCnt : " << rawCnt << endl;
                    buf.push_back(make_pair(i, j-1));
                    visitedList[i][j-1] = 1;
                }
            }
            if(j+1 <= M){
                if(visitedList[i][j+1] == 0){
                    rawCnt--;
                    //cout << "rawCnt : " << rawCnt << endl;
                    buf.push_back(make_pair(i, j+1));
                    visitedList[i][j+1] = 1;
                }
            }
        }
        que = buf;
        /*for(int q = 1; q <= N ; q++){
            for(int w = 1; w <=M; w++){
                cout << visitedList[q][w] << " ";
            }
            cout << endl;
        }
        cout <<endl;*/
    }
 
    cout << day;
    return 0;
}