백준 - 7576 토마토

 

날짜 계산식을 따로 만들어야하는구나 생각했다.

근데 아니었다. 걍 거리 계산하는거랑 똑같은거였다. 내가 생각이 많았다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

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

struct Pos
{
	Pos() = default;
	Pos(int a, int b) : y(a), x(b)
	{

	}

	int x;
	int y;


	bool operator!= (const Pos& other)const
	{
		if (x == other.x)
		{
			if (y == other.y)
			{
				return false;
			}
		}
		return true;
	}

	bool operator== (const Pos& other)const
	{
		return !(*this != other);
	}

	bool operator<(const Pos& other)const
	{
		if (x != other.x)
		{
			return x < other.x;
		}
		return y < other.y;
	}

};


int main(void)
{
	int n, m;

	cin >> n >> m;
	
	vector<vector<int>> vec(m, vector<int>(n));

	int all1 = 0;

	vector<Pos> onbox;

	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			int num;
			cin >> num;
			if (num == 1 || num == 0)
			{
				all1++;
				if (num == 1)
				{
					onbox.push_back(Pos(i, j));
				}
			}
			vec[i][j] = num;
		}
	}

	int answer = onbox.size();

	int day = 0;


	vector<vector<bool>> visited(m, vector<bool>(n, false));

	vector<vector<int>> days(m, vector<int>(n, 0));

	for (int i = 0; i < onbox.size(); ++i)
	{
		int y = onbox[i].y;
		int x = onbox[i].x;
		days[y][x] = 0;
	}

	queue<Pos> q;

	for (int i = 0; i < onbox.size(); ++i)
	{
		q.push(onbox[i]);
	}

	while (!q.empty())
	{
		Pos pos = q.front();
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int x = pos.x + dx[i];
			int y = pos.y + dy[i];

			Pos next(y, x);

			if (x < 0 || x >= n || y < 0 || y >= m)
			{
				continue;
			}

			if (vec[y][x] == -1 || vec[y][x] == 1)
			{
				continue;
			}

			q.push(next);
			vec[y][x] = 1;
			answer++;
			
			days[next.y][next.x] = days[pos.y][pos.x] + 1;
			if (day < days[next.y][next.x])
			{
				day = days[next.y][next.x];
			}
		}
		
	}

	if (all1 == answer)
	{
		cout << day;
	}
	else
	{
		cout << -1;
	}

	return 0;
}