[백준 7576: 토마토] - C++

www.acmicpc.net/problem/7576

7576번: 토마토

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;

int n,m;
int map[1000][1000];

int dis[1000][1000];
bool check[1000][1000];

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };


int main() {

	memset(dis, 0, sizeof(dis));
	memset(check, false, sizeof(check));

	cin >> m >> n;

	int input = 0;

	queue<pair<int, int>> Q;

	for (int i = 0; i < n; i++)
	{

		for (int j = 0; j < m; j++)
		{

			cin >> input;
			map[i][j] = input;

			if (input == 1) {
				Q.push({ i, j });				
			}
			else if ( input == -1 ) {
				dis[i][j] = -1;
			}
		}
	}



	int TotalDay = 0;

	while (!Q.empty())
	{
		int xx = Q.front().first;
		int yy = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextX = xx + dx[i];
			int nextY = yy + dy[i];

			if (nextY < 0 || m <= nextY || nextX < 0 || n <= nextX)
			{
				continue;
			}

			if (map[nextX][nextY] == 0 && !check[nextX][nextY])
			{
				check[nextX][nextY] = true;
				Q.push({ nextX,nextY });
				if (TotalDay < dis[xx][yy] + 1)
					TotalDay = dis[xx][yy] + 1;
				dis[nextX][nextY] = dis[xx][yy] + 1;
			}


		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (check[i][j] == false && map[i][j] == 0) {
				cout << -1 << endl;
				return 0;			
			}
		}
	}

	cout << TotalDay << endl;
	
	return 0;
}