7576 토마토

#include <stdio.h>
#include <queue>
#include <utility>
 
using namespace std;
 
queue<pair<int, pair<int, int>>> q;
int arr[1005][1005] = { 0 };
int chk[1005][1005] = { 0 };
int dx[4] = { 1,-1, 0,0 };
int dy[4] = { 0,0,1,-1 };
 
int bfs(int sum, int endY, int endX) {
    int rst = 0, len;
    while (!q.empty()) {
        len = q.front().first;
        int y = q.front().second.first;
        int x = q.front().second.second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
 
            if (1 > xx || xx > endX || 1 > yy || yy > endY)
                continue;
            if (chk[yy][xx] == 1 || arr[yy][xx] == -1)
                continue;
 
            chk[yy][xx] = 1;
            rst++;
            q.push(make_pair(len + 1, make_pair(yy, xx)));
        }
    }
    if (sum == rst)
        return len;
    else
        return -1;
}
 
int main() {
    int y, x;
    scanf("%d %d", &x, &y);
 
    int sum = y * x;
    for (int i = 1; i <= y; i++) {
        for (int j = 1; j <= x; j++) {
            scanf("%d", &arr[i][j]);
 
            if (arr[i][j] == 1) {
                q.push(make_pair(0, make_pair(i, j)));
                chk[i][j] = 1;
                sum--;
            }
            else if (arr[i][j] == -1) {
                sum--;
            }
        }
    }
    printf("%d",bfs(sum, y, x));    
}