[백준] 2178번 미로 탐색 C++

semi·2022년 10월 5일
0

coding test

목록 보기
49/57

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

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int N, M;
int maze[101][101] = { 0, };
int direct[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
queue<pair<int, int>> q;
void BFS()
{
	int nx, ny;
	pair<int, int> cur;
	q.push({ 0, 0 });
	while (!q.empty())
	{
		cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			nx = cur.first + direct[i][0]; // j
			ny = cur.second + direct[i][1]; // i
			if (nx >= 0 && nx < M && ny >= 0 && ny < N && maze[ny][nx] == 1)
			{
				q.push({ nx, ny });
				maze[ny][nx] = maze[cur.second][cur.first] + 1;
			}
		}
	}
}

int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < M; j++)
		{
			maze[i][j] = str[j] - '0';
		}
	}
	BFS();
	cout << maze[N - 1][M - 1];
	return 0;
}

0개의 댓글