2178번 - 미로 탐색

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

2178번: 미로 탐색

#include <iostream>
#include <string>
#include <queue>
using namespace std;
int N, M;
int maze[101][101];
bool visit[101][101];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int ans[101][101];
queue<pair<int, int>> q;
bool is_possible(int row, int col)
{
	if (row < 0 || row >= N || col < 0 || col >= M)
		return false;
	return true;
}
void solve(int row, int col)
{
	q.push(make_pair(row, col));
	visit[row][col] = true;
	ans[row][col]++;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			//이동가능하고 길이 있고 들렸던 경로가 아닐 경우
			if (true == is_possible(nx, ny) && 1 == maze[nx][ny] && false == visit[nx][ny])
			{
				q.push(make_pair(nx, ny));
				visit[nx][ny] = true;
				ans[nx][ny] = ans[x][y] + 1;
			}
		}
	}
	

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