#include
#include
#include
using namespace std;
const int MAX = 1001;
int n, m;
int tomato[MAX][MAX];
queue<pair<int, int>> t;
struct Move {
int x, y;
};
Move mv[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
void bfs(int i,int j) {
for (int k = 0; k < 4; k++) {
int movei = i + mv[k].x;
int movej = j + mv[k].y;
if (movei >= 0 && movei < m && movej >= 0 && movej < n && tomato[movei][movej] == 0) {
tomato[movei][movej] = 1;
t.push(make_pair(movei, movej));
}
}
}
int main(void) {
int answer = -1;
cin >> n >> m;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> tomato[i][j];
if (tomato[i][j] == 1)
t.push(make_pair(i, j));
}
}
while (!t.empty()) {
int size = t.size();
for (int k = 0; k < size; k++) {
int i = t.front().first;
int j = t.front().second;
t.pop();
bfs(i, j);
}
answer++;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (tomato[i][j] == 0)
answer = -1;
}
}
cout << answer << endl;
return 0;
}
'백준 알고리즘 > BFS' 카테고리의 다른 글
백준 11403번 C++ (0) | 2019.08.08 |
---|---|
백준 1012번 C++ (0) | 2019.08.08 |
백준 2667번 C++ (0) | 2019.08.08 |
백준 1697번 C++ (0) | 2019.08.07 |
백준 2178번 C++ (0) | 2019.08.07 |