[프로그래머스][C++] 게임 맵 최단거리

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

[프로그래머스][C++] 게임 맵 최단거리

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

int solution(vector<vector<int> > maps)
{
	int dy[4] = { -1,1,0,0 };
	int dx[4] = { 0,0,-1,1 };

	int n = maps.size();
	int m = maps[0].size();
	vector<vector<int>> visit(n, vector<int>(m, 0));
	queue<pair<int, int>> q;
	q.push({ 0, 0 });
	visit[0][0] = 1;

	while (!q.empty()) {
		int fi = q.front().first;
		int fj = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ni = fi + dy[i];
			int nj = fj + dx[i];

			if (ni < 0 || nj < 0 || ni >= n || nj >= m || !maps[ni][nj] || visit[ni][nj]) {
				continue;
			}

			visit[ni][nj] = visit[fi][fj] + 1;
			q.push({ ni, nj });
		}
	}

	return visit[n - 1][m - 1] ? visit[n - 1][m - 1] : -1;
}