백준 / 바킹독님의 문제집 / 미로 탐색(2178)

문제 설명

 

 

 

문제 해결

 

방문 했는지 안했는지 검사하고 current의 값 + 1 값을 다른 좌표에다가 옮기는 형태로 문제를 해결했다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <string>

#define x first
#define y second

using namespace std;

int N, M;

int map[100][100];
int visit[100][100]{ 0 };
int result[100][100]{ 0 };
int min_ = 1;

queue<pair<int, int>> q;

pair<int, int> udlr[4] = { {1,0},{0,1},{-1,0},{0,-1} };


int main(int argc, char* argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M;
	string temp;
	getline(cin, temp);

	for (int i = 0; i < N; i++)
	{
		getline(cin, temp);
		for (int j = 0; j < M; j++)
			map[i][j] = (temp[j] - 48);
	}

	visit[0][0] = 1;
	result[0][0] = 1;
	q.push(make_pair(0, 0));

	while (!q.empty())
	{
		pair<int, int> current = q.front();
		q.pop();
		min_ += 1;
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = current.x + udlr[dir].x;
			int ny = current.y + udlr[dir].y;

			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;

			if ((visit[nx][ny] == 1) || (map[nx][ny] == 0))
				continue;

			visit[nx][ny] = 1;
			result[nx][ny] = result[current.x][current.y]+1;

			q.push(make_pair(nx, ny));
		}
	}

	cout << result[N - 1][M - 1] << '\n';

	return 0;
}