前情提要
* 回溯:递归
* 剪枝
* 可行性剪枝
* 自由性剪枝
BFS例题——迷宫
题目描述
一个迷宫由 R 行 C 列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。
给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。
输入格式
第一行是两个整数,
R 和 C(1≤R,C≤40),代表迷宫的长和宽。
接下来是 R 行,每行 C 个字符,代表整个迷宫。
空地格子用.表示,有障碍物的格子用 #表示。
迷宫左上角和右下角都是.。
输出格式
输出从左上角走到右下角最小移动的步数。计算步数不包含起点。
输入输出样例
输入#1
输出#1
说明/提示
数据范围:(1≤R,C≤40)
样例说明:
移动路径为
[1,1]−>[1,2]−>[2,2]−>[2,3]−>[2,4]−>[3,4]−>[4,4]−>[5,4]−>[5,5],一共花费8步
参考代码如下:
BFS练习
01.01.01. 图像渲染
02.02.02.岛屿数量