[7576] 토마토

BFS를 사용하면 쉽게 풀 수있는 문제였다.

처음에 토마토가 비어있는 부분이 있으면 (배열중 들리지 않은곳이 있으면) 

무조건 모두 익지 않은 경우라고 체크해서 -1을 출력하고 틀렸었다.

처음 주어진 익은 토마토를 큐에 전부 넣는다

check[x][y]에는 토마토가 익은 날을 저장한다.

인접한 토마토는  check[x][y] 다음날에 익으므로

check[nx][ny] = check[x][y]+1이다.

check[x][y]중 가장 큰 수가 토마토가 모두 익은 날이다.

---

#include <cstdio>

#include <queue>

using namespace std;

int main(){

int box[1001][1001];

int check[1001][1001];

queue<pair<int,int> > q;

int N,M;

scanf("%d %d",&N,&M);

for(int i = 0;i<M;i++){

for(int j = 0;j<N;j++){

check[i][j] = -1;

scanf("%d",&box[i][j]);

if(box[i][j] > 0){

check[i][j] = 0;

q.push(make_pair(i,j));

}

}

}

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

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

int nx,ny;

while(!q.empty()){

int x = q.front().first;

int y = q.front().second;

q.pop();

for(int i = 0;i<4;i++){

nx = x+dx[i];

ny = y+dy[i];

if(box[nx][ny] != -1 && check[nx][ny] == -1){

q.push(make_pair(nx,ny));

check[nx][ny] = check[x][y] + 1;

}

}

}

int res = 0 ;

for(int i = 0;i<M;i++){

for(int j = 0;j<N;j++){

if(box[i][j] == 0 && check[i][j] == -1) {printf("-1\n"); return 0;}

if(check[i][j] > res){

res = check[i][j];

}

}

}

printf("%d\n",res);

}