NOI2.5-2753走迷宫
5969+
作者：crxis 发布：2018-05-23 分类：广度优先搜索
题目大意：一个n*m的迷宫，遇到#不可以走，遇到.才可以走，从左上角往4个方向走，到达右下角至少要走多少步？
题目描述
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
输入
第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用’.’表示，有障碍物的格子用’#’表示。
迷宫左上角和右下角都是’.’。
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用’.’表示，有障碍物的格子用’#’表示。
迷宫左上角和右下角都是’.’。
输出
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
样例输入
5 5
..###
#....
#.#.#
#.#.#
#.#..
样例输出
9
解题思路
广度优先遍历，1周围可以走的是2，然后2周围可以走的没走过的是3……最终走到右下角，最少步数就出来了。
走到的地方，依次放入队列，保证步数少的先出队，每个格子填入的数字都是最少步数。
程序实现
最少步数，一般不用深搜，因为方向随机，会重复走更新步数，数据比较小的可以尝试一下。
一开始，#不可以走，用0表示；.可以走，用无穷大表示。起点步数为1，从起点开始，0不可以走，判断条件是步数+1更小才能走过去（可能有更近的路到达终点），这样就不会走到0的地方。走过的地方还可能重复走，因为有可能第一次到达的不是最少步数，格子步数变小后，需要继续更新从该点出发的可以到达的格子。
