[21327][伯俊/BOJ]探索2178号迷宫

質問する

にゅうしゅつりょく

に答える

次の要素のdist値は、現在の要素のdist値+1です.

コード#コード#

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define SIZE 102

char board[SIZE][SIZE];
int dist[SIZE][SIZE];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main()
{
	int n, m;
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

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

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

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

	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; ++dir)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[nx][ny] >= 0 || board[nx][ny] == '0') continue;
			dist[nx][ny] = dist[cur.X][cur.Y] + 1; // 다음 원소의 dist 값은 현재 원소의 dist + 1
			Q.push({ nx,ny });
		}
	}
	cout << dist[n - 1][m - 1] + 1;
}