본문 바로가기
백준 알고리즘/BFS

백준 7576번 C++

by paysmile 2019. 8. 8.


#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