7576번: 토마토

BFS를 이용해서 쉽게 풀 수 있는 문제.

#include <iostream>
#include <queue>
#include <algorithm>
 
typedef struct {
    int y, x;
} dif;
 
dif dir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
 
int check[1001][1001] = { 0 };
int map[1001][1001] = { 0 };
 
int main(void) {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    
    int col, row;
    std::cin >> col >> row;
    std::queue<std::pair<dif, int>> mQ;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            std::cin >> map[i][j];
            if (map[i][j] == 1) { 
                mQ.push({ {i, j}, 0 }); 
                check[i][j] = 1;
            }
        }
    }
 
    int count = 0;
    while (!mQ.empty()) {
        int y = mQ.front().first.y;
        int x = mQ.front().first.x;
        count = mQ.front().second;
        mQ.pop();
        for (int i = 0; i < 4; i++) {
            int tempY = y + dir[i].y;
            int tempX = x + dir[i].x;
            //std::cout << tempY << ", " << tempX << "\n";
            if (tempX < 0 || tempX >= col || tempY < 0 || tempY >= row) { continue; }
            if (check[tempY][tempX] || map[tempY][tempX] == -1) continue;
            check[tempY][tempX] = 1;
            mQ.push({ {tempY, tempX}, count + 1 });
        }
    }
 
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (check[i][j] == 1 || map[i][j] == -1) continue;
            std::cout << -1 << "\n";
            return 0;
        }
    }
 
    std::cout << count << "\n";
 
    return 0;
}