[BaekJoon][7578] 토마토

BAEKJOON ONLINE JUDGE

한국정보올림피아드 시.도 지역본선 2013

7578 토마토

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

13분

#include <cstdio>
#include <queue>
using namespace std;
 
#define Flag        10000000
 
int height, width;
int map[1000][1000];
queue<pair<int, int> > que;
int cnt;
 
int bfs()
{
    int y, x;
    int dy[4] = { -1, 0, 0, 1 };
    int dx[4] = { 0, -1, 1, 0 };
 
    while (!que.empty()) {
        y = que.front().first;
        x = que.front().second;
        que.pop();
 
        for (int i = 0; i < 4; i++) {
            int nexty = y + dy[i];
            int nextx = x + dx[i];
 
            if (nexty >= 0 && nexty < height && nextx >= 0 && nextx < width) {
                if (map[nexty][nextx] == 0) {
                    que.push(make_pair(nexty, nextx));
                    map[nexty][nextx] = map[y][x] + 1;
                    cnt--;
                }
            }
        }
    }
 
    if (cnt == 0)        return map[y][x] - Flag - 1;
    return -1;
}
 
int main()
{
    int i, j;
 
    scanf("%d %d", &width, &height);
 
    for (i = 0; i < height; i++) {
        for (j = 0; j < width; j++) {
            scanf("%d", &map[i][j]);
 
            if (map[i][j] == 1) {
                que.push(make_pair(i, j));
                map[i][j] += Flag;
            }
            else if (map[i][j] == 0) {
                cnt++;
            }
        }
    }
 
    printf("%d\n", bfs());
 
    return 0;
}