背景

老师不准让我们用 DFS，只能用 BFS

题意

找到左上角到右下角的最快路径

思路

用 BFS 的话...

首先开结构体存 $x$、$y$、层数，然后遍历上下左右。如果这格到终点，就输出

代码

#include <bits/stdc++.h>
using namespace std;
int a[45][45],cnt;
bool f[45][45];
int r,c;
struct pos{
	int x,y,ceng;
};
void bfs(){
	queue<pos> q;
	q.push({1,1,1});
	while(!q.empty()){
		int x = q.front().x,y = q.front().y,ceng = q.front().ceng;
		if (x == r && y == c){	// 如果这个格子到了终点，直接退出
			cnt = ceng;
			return;
		}
		// 上
		if (a[x - 1][y] && !f[x - 1][y])	q.push({x - 1,y,ceng + 1}),f[x - 1][y] = 1;
		// 左
		if (a[x][y - 1] && !f[x][y - 1])	q.push({x,y - 1,ceng + 1}),f[x][y - 1] = 1;
		// 下
		if (a[x + 1][y] && !f[x + 1][y])	q.push({x + 1,y,ceng + 1}),f[x + 1][y] = 1;
		// 右
		if (a[x][y + 1] && !f[x][y + 1])	q.push({x,y + 1,ceng + 1}),f[x][y + 1] = 1;
		q.pop();	// 用完了，再见
	}
}
int main(int argc, char **argv){
	cin >> r >> c;
	for (int i = 1;i <= r;i++){
		for (int j = 1;j <= c;j++){
			char c;
			cin >> c;
			a[i][j] = (c == '.'?1:0);	// 这里路是 1，障碍是 0
		}
	}
	bfs();
	cout << cnt;
	return 0;
}