7576 토마토

문제 링크

• 풀이

BFS를 이용하여 풀면 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int M, N, box[1002][1002];
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };

struct tmt {
    int r, c, t;
};

int ripe(queue<tmt>& q)
{
    int t = 0;

    while (!q.empty())
    {
        int r = q.front().r;
        int c = q.front().c;
        t = q.front().t;
        q.pop();

        for (int d = 0; d < 4; d++)
        {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (box[nr][nc])
                continue;

            box[nr][nc] = 1;
            q.push({ nr, nc, t + 1 });
        }
    }

    for (int r = 1; r <= N; r++)
        for (int c = 1; c <= M; c++)
            if (!box[r][c])
                return -1;

    return t;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(box, -1, sizeof(box));
    queue<tmt> q;

    cin >> M >> N;

    for (int r = 1; r <= N; r++)
    {
        for (int c = 1; c <= M; c++)
        {
            cin >> box[r][c];
            if (box[r][c] == 1 )
            {
                q.push({ r, c, 0 });
            }
        }
    }

    cout << ripe(q) << "\n";

    return 0;
}