본문 바로가기

알고리즘 풀이

백준 7576번 토마토

https://www.acmicpc.net/source/2802084


#include <iostream>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = { 0, -1, 1, 0 };
int box[1001][1001];
int visit[1001][1001];
int N, M;
inline bool inRange(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
int main(void) {
int cnt = 0;
queue<pair<int, int>>q;
scanf("%d %d", &M, &N);
for (int i = 0; i < N; ++i){
for (int j = 0; j < M; ++j) {
scanf("%d", &box[i][j]);
visit[i][j] = -1;
if (box[i][j] == 1){
q.push(make_pair(i, j));
visit[i][j] = 0;
}
}
}
// 1: 익은거, 0:안익은거, -1:토마토 없음
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; ++i) {
int newX = x + dx[i];
int newY = y + dy[i];
if (inRange(newX, newY)) {
if (box[newX][newY] == 0 && visit[newX][newY] == -1) {
visit[newX][newY] = visit[x][y] + 1;
q.push(make_pair(newX, newY));
}
}
}
}
int ans = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (ans < visit[i][j])
ans = visit[i][j];
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (box[i][j] == 0 && visit[i][j] == -1){
ans = -1;
}
}
}
printf("%d\n", ans);
return 0;
}


'알고리즘 풀이' 카테고리의 다른 글

백준 2512번 예산  (0) 2018.04.16
백준 1259번 팰린드롬 수  (0) 2018.04.08
백준 5567번 결혼식  (0) 2018.03.25
백준 6359번 만취한 상범  (0) 2018.02.07
백준 2302번 극장 좌석  (0) 2018.02.02