🙄迷宮から逃げる(最短距離)

https://www.acmicpc.net/problem/2178
問題の説明
NbyMサイズの矩形迷路に閉じ込められている.迷宮には怪物がいて、それを避けて逃げようとしている.プレイヤーの初期位置は(1,1),迷宮出口は(N,M)位置にあり,一度に1格移動できる.このときモンスターがいる部分は0、ない部分は1と表示されます.迷宮はきっと逃げられる形で現れたに違いない.このとき,プレイヤーが迷路から脱出するために移動しなければならない最小格数を求める.ただし、セルの計算には、開始セルと最後のセルも含める必要があります.
入力条件
第1行は2つの整数N,M(4<=N,M<=200)を与える.次のN行では,迷路の情報をそれぞれM個の整数(0または1)で与える.各数字には入力としてスペースが付いています.また、開始バーと最後のバーは常に1です.
しゅつりょくじょうけん
1行目に最小移動格子数を出力します.
入力例

5 6
101010
111111
000001
111111
111111

出力例

10

😏 インプリメンテーション

#include <bits/stdc++.h>

using namespace std;

int graph[201][201];
int n, m;
int dx[]{-1,1,0,0};
int dy[]{0,0,-1,1};

int bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push({ x,y });

	while (q.empty() == false)
	{
		 x = q.front().first;
		 y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (graph[nx][ny] == 0) continue;
			if (graph[nx][ny] == 1)
			{
				graph[nx][ny] = graph[x][y] + 1;
				q.push({ nx,ny });
			}
		}
	}
	return graph[n - 1][m - 1];
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf_s("%1d", &graph[i][j]);

	cout << bfs(0, 0) << '\n';

	return 0;
}

2022.01.09再実施

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

string graph[102];
int dist[102][102];

int dx[]{-1,1,0,0};
int dy[]{0,0,-1,1};

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> graph[i];

	for (int i = 0; i < n; i++)
		fill(dist[i], dist[i] + m, -1);

	dist[0][0] = 0;
	queue<pair<int, int>> Q;
	Q.push({ 0,0 });

	while (!Q.empty())
	{
		pair<int, int> cur = Q.front(); Q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[nx][ny] >= 0 || graph[nx][ny] != '1') continue;
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			Q.push({ nx,ny });
		}
	}

	cout << dist[n - 1][m - 1] + 1 ;

	return 0;
}