U567311 走迷宫(BFS)

题目背景

搬运自 AcWing。

题目描述

给定一个 $n\times m$ 二维整数数组，用来表示一个迷宫，数组中只包含 $0$ 或 $1$，其中 $0$ 表示可以走的路，$1$ 表示墙壁。

最初，有一个人位于左上角 $(1,1)$，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 $(n,m)$ 处，至少需要移动多少次。

数据保证 $(1,1)$ 处和 $(n,m)$ 处的数字为 $0$，且一定至少存在一条通路。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行包含 $m$ 个整数（$0$ 或 $1$），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

输入输出样例

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

8

说明/提示

数据范围：

$1\le n,m\le 100$

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

const int N = 105;

// maze：记录迷宫
// 0 表示可以走
// 1 表示墙
int maze[N][N];

// dist[x][y]：从起点走到 (x,y) 的最少步数
// -1 表示还没有访问过
int dist[N][N];

int n, m;

// 四个方向：下、上、右、左
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs() {
	// 队列中存坐标
	queue<pair<int, int> > q;
	
	// 初始化所有位置为 -1
	// 表示这些位置还没有访问过
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dist[i][j] = -1;
		}
	}
	
	// 起点是 (1,1)
	dist[1][1] = 0;
	
	// 起点入队
	q.push({1, 1});
	
	// 只要队列不为空，就继续搜索
	while (!q.empty()) {
		
		// 取出队头
		int x = q.front().first; //x
		int y = q.front().second;//y
		
		q.pop();
		
		// 枚举上下左右四个方向
		for (int i = 0; i < 4; i++) {
			
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			// 越界，不能走
			if (nx < 1 || nx > n || ny < 1 || ny > m) {
				continue;
			}
			
			// 是墙，不能走
			if (maze[nx][ny] == 1) {
				continue;
			}
			
			// 已经访问过，不重复走
			if (dist[nx][ny] != -1) {
				continue;
			}
			
			// 新位置的距离
			// = 当前距离 + 1
			dist[nx][ny] = dist[x][y] + 1;
			
			// 新位置入队
			q.push({nx, ny});
		}
	}
}

int main() {
	
	cin >> n >> m;
	
	// 输入迷宫
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> maze[i][j];
		}
	}
	
	// 开始 BFS
	bfs();
	
	// 输出到右下角的最短距离
	cout << dist[n][m] << endl;
	
	return 0;
}