BOJ 7576번 토마토

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/7576/7576/%EC%86%8C%EC%8A%A4.cpp

 

정보올림피아드 지역본선 2013년도 고등부1번 문제이다

현재 배열을 1로 주고 1 지역에서 탐색으로 발견되는 0 지역은 1보다 큰 2일째가 되는 것으로 지정해주는 방식으로

따로 메모리 쓸 일도 없고 그냥 전체 배열하나로 해결할 수 있는 문제이다

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int mx[4] = { -1,1,0,0 };
int my[4] = { 0,0,1,-1 };
int arr[1000][1000];
int zero;
queue<pair<int, int> > q;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int M, N; cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < M; k++) {
            cin >> arr[i][k];
            if (arr[i][k] == 1) q.push({ i,k });
            else if (!arr[i][k]) zero++;
        }
    }
 
    int MAX = 0;
 
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = my[i] + y;
            int xx = mx[i] + x;
            if (yy >= 0 && xx >= 0 && yy < N && xx < M && !arr[yy][xx]) {
                q.push({ yy,xx });
                zero--;
                arr[yy][xx] = arr[y][x] + 1;
            }
        }
        MAX = MAX < arr[y][x] - 1 ? arr[y][x] - 1 : MAX;
    }
 
    if (zero) cout << "-1";
    else cout << MAX;
 
    return 0;
}