7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
#include <cstdio>
#include <queue>
using namespace std;
int a[1000][1000];
int d[1000][1000];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main() {
int n,m;
scanf("%d %d",&m,&n);
queue<pair<int,int>> q;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
scanf("%d",&a[i][j]);
d[i][j] = -1;
if (a[i][j] == 1) {
q.push(make_pair(i,j));
d[i][j] = 0;
}
}
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (a[nx][ny] == 0 && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.push(make_pair(nx,ny));
}
}
}
}
int ans = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (ans < d[i][j]) {
ans = d[i][j];
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (a[i][j] == 0 && d[i][j] == -1) {
ans = -1;
}
}
}
printf("%d\n",ans);
return 0;
}'Problem set' 카테고리의 다른 글
| [백준] 16940 BFS 스페셜 저지 (0) | 2021.02.20 |
|---|---|
| [백준] 7562 나이트의 이동 (0) | 2021.02.20 |
| [백준] 2178 미로 탐색 (0) | 2021.02.20 |
| [백준] 4963 섬의 개수 (0) | 2021.02.20 |
| [백준] 2667 단지번호붙이기 (0) | 2021.02.20 |