[백준][BFS] 토마토

백준 알고리즘

BFS

C++

 

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

#include <iostream>
#include <queue>
using namespace std;

int M, N;
int map[1000][1000];
int visited[1000][1000] = { 0, };

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
queue<pair<int, int>> q;
int cnt=0;

void bfs();

int main()
{
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 1) {
				q.push(make_pair(i, j));
				//visited[i][j] = 1;
			}			
		}
	}

	bfs();

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				cout << -1;
				return 0;
			}
		}
	}
	cout << cnt;
	return 0;
}

void bfs() {
	int x, y, nx, ny;
	while (!q.empty())
	{
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			nx = x + dx[k];
			ny = y + dy[k];
			if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
				if (map[nx][ny] == 0 && visited[nx][ny] == 0) {
					map[nx][ny] = 1;
					visited[nx][ny] = visited[x][y] + 1;
					cnt = visited[nx][ny];
					q.push(make_pair(nx, ny));
				}
			}
		}		
	}
}