7576 : 토마토

풀이

bfs를 돌리자

코드

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

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

int n, m, a[1003][1003];
queue<pair<int, int> > que;

int main() {
    scanf("%d %d", &m, &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 1) que.push({ i,j });
        }
    }

    while (!que.empty()) {
        auto now = que.front();
        que.pop();

        int y = now.first, x = now.second;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if (a[ny][nx] == 0) {
                a[ny][nx] = a[y][x] + 1;
                que.push({ ny,nx });
            }
        }
    }

    int mx = -1e9;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!a[i][j]) return !printf("-1");;
            mx = max(mx, a[i][j]);
        }
    }

    printf("%d", mx - 1);

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-04-17 23:28

Read more posts by this author