토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int row, col;
int tomatoCnt;
int days;
vector<pair<int,int>> tomatoPos;
vector<vector<int>> tomatoMap;

int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};

void input()
{
    cin >> col >> row;
    tomatoCnt=0;
    days = 0;
    tomatoMap.resize(row, vector<int>(col,0));

    for(int i=0; i <row; i++)
    {
        for(int j=0; j < col; j++)
        {
            cin >> tomatoMap[i][j];
            if(tomatoMap[i][j] == 1)
            {
                tomatoPos.push_back(make_pair(i,j));
            }

            if(tomatoMap[i][j] == 0)tomatoCnt++;
        }
    }
}

void bfs()
{
    queue<pair<int,int>> q;

    for(auto a : tomatoPos)
    {
        q.push(a);
    }

    while(!q.empty())
    {
        size_t qSize = q.size();
        bool isRipe = false;

        for(int i=0; i < qSize; i++)
        {
            int r = q.front().first;
            int c = q.front().second;
            q.pop();

            for(int d=0; d < 4; d++)
            {
                int nR = r + dr[d];
                int nC = c + dc[d];

                if(nR < 0 || nR >= row || nC < 0 || nC >=col)continue;

                if(tomatoMap[nR][nC] == 1 || tomatoMap[nR][nC] == -1) continue;

                tomatoMap[nR][nC] = 1;
                tomatoCnt--;
                isRipe = true;
                q.push(make_pair(nR, nC));
            }
        }

        if(isRipe)days++;
    }
}

int main()
{
    input();

    bfs();

    if(tomatoCnt == 0)cout << days;
    else cout << "-1";
}