토마토 7576번 [백준]

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

7576번: 토마토

 

bfs으로 풀게 되면 매우 쉽게 풀 수 있는 문제이다.

 

#include<bits/stdc++.h>
#include<sys/types.h>


using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(ll i=0;i<j;i++)
#define pii pair<int,int>
#define ff first
#define ss second

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

void solve() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> box(n, vector<int>(m));
    vector<vector<bool>> isVisited(n, vector<bool>(m, false));
    rep(i, n) {
        rep(j, m) {
            cin>>box[i][j];
        }
    }
    queue<pair<pii, int>> q;
    rep(i, n) {
        rep(j, m) {
            if (box[i][j] == 1) {
                q.push({{i, j}, 0});
                isVisited[i][j] = true;
            }
        }
    }
    int ans = 0;
    while (!q.empty()) {
        pii tomato = q.front().ff;
        int cur = q.front().ss;
        ans = max(cur, ans);
        q.pop();
        rep(i, 4) {
            int x = tomato.ff + dx[i];
            int y = tomato.ss + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m)
                continue;
            if (!isVisited[x][y] && box[x][y] == 0) {
                box[x][y] = 1;
                isVisited[x][y] = true;
                q.push({{x, y}, cur + 1});
            }
        }
    }
    rep(i, n) {
        rep(j, m) {
            if (box[i][j] == 0) {
                cout << -1 << endl;
                return;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    fast_io;
    solve();
    return 0;
}