14940: 쉬운 최단거리

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

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int Maps[1000][1000];
int Check[1000][1000];
vector<vector<int>> VecDist(1000, vector<int>(1000, 2147000000));

int DirRow[4]{ -1, 0, 1, 0 };
int DirCol[4]{ 0, 1, 0, -1 };

struct Data
{
	int Row, Col, Val;
	Data(int InRow, int InCol, int InVal)
	{
		Row = InRow;
		Col = InCol;
		Val = InVal;
	}
	bool operator<(const Data& Comp) const
	{
		return Val > Comp.Val;
	}
};

void Func(int InStartRow, int InStartCol)
{
	queue<Data> Q;
	Q.push(Data(InStartRow, InStartCol, 0));

	VecDist[InStartRow][InStartCol] = 0;
	Check[InStartRow][InStartCol] = 1;

	while (!Q.empty())
	{
		Data CurrentData = Q.front();
		Q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int CheckRow = CurrentData.Row + DirRow[i];
			int CheckCol = CurrentData.Col + DirCol[i];

			if (CheckRow < 0 || CheckCol < 0 || CheckRow >= n || CheckCol >= m || 
				Check[CheckRow][CheckCol] || VecDist[CheckRow][CheckCol] == 0)
				continue;

			Check[CheckRow][CheckCol] = 1;
			Q.push(Data(CheckRow, CheckCol, CurrentData.Val + 1));
			VecDist[CheckRow][CheckCol] = CurrentData.Val + 1;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	//freopen("input.txt", "rt", stdin);

	cin >> n >> m;

	Data StartData(0, 0, 0);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> Maps[i][j];

			if (Maps[i][j] == 0) 
			{
				VecDist[i][j] = 0;
			}
			else if (Maps[i][j] == 2)
			{
				StartData.Row = i;
				StartData.Col = j;
			}
		}
	}

	Func(StartData.Row, StartData.Col);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (VecDist[i][j] == 2147000000)
			{
				cout << -1 << ' ';
			}
			else
			{
				cout << VecDist[i][j] << ' ';
			}
		}

		cout << '\n';
	}

	return 0;
}