BOJ 7576 토마토

1 개요

BOJ 7576 토마토

• 백준 온라인 저지 7576번 문제
• BOJ 31단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int M, N;
int A[1000][1000];
int want = 0;
int got = 0;
int days = 1;
queue<pair<int,int>> q;

int dx[4] = {1, -1, 0,  0};
int dy[4] = {0,  0, 1, -1};

void bfs() {
    int x, y, nx, ny;
    while(!q.empty()) {
        pair<int,int> p = q.front();
        q.pop();
        x = p.first;
        y = p.second;
        for(int i=0; i<4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if(nx<0 || nx>=M || ny<0 || ny>=N || A[nx][ny] != 0) continue;
            A[nx][ny] = A[x][y] + 1;
            q.push({nx,ny});
            got++;
            if(A[nx][ny] > days) days = A[nx][ny];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> M >> N;
    for(int y=0; y<N; y++) {
        for(int x=0; x<M; x++) {
            cin >> A[x][y];
            if(A[x][y] == 0) {
                want++;
            } else if(A[x][y] == 1) {
                q.push({x,y});
            }
        }
    }
    bfs();
    cout << ((want == got) ? days-1 : -1);
}