[백준] 2137 c++

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

2178번: 미로 탐색

 

풀이

입력이 빈칸없이 주어져서 string으로 받은 다음에 int로 한 칸씩 짤라서 넣어줘야한다.

bfs로 풀면 된다.
(1,1)에서 (N,M)까지 가는 최단 경로의 칸수를 출력하면 된다.
각 칸에다가 (1,1)에서 각 칸까지의 칸수를 저장하고 다음 칸에 +1해서 칸의 수를 저장했다.

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

int N, M;
int num[102][102];
int cnt;
void bfs(int yy, int xx)
{
	queue<pair<int, int>> q;
	q.push(make_pair(yy, xx));
	int dy[] = { 0,1,0,-1 };
	int dx[] = { 1,0,-1,0 };
	cnt++;
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		
	
		for (int t = 0; t < 4; t++)
		{
			if (num[y + dy[t]][x + dx[t]] == 1)
			{
				q.push(make_pair(y + dy[t], x + dx[t]));
				num[y + dy[t]][x + dx[t]] = num[y][x] + 1;
				
			}
		}

	}
	

	
}

int main()
{
	cin >> N >> M;
	string tmp;
	for (int i = 1; i <= N; i++)
	{
		cin >> tmp;
		for (int j = 1; j <=M; j++)
		{
			num[i][j]=tmp[j-1]-'0';

		}
	}
	
	bfs(1, 1);
	cout << num[N][M];
	
}