WJ的逃离

题目描述

当WJ醒来时,发现自己被困在一个地图的左上角,幸好WJ有张图,并了解到出口正是迷宫的右下角,至少有一条路径可以到达出口。
整个地图有些地方会有障碍(保证左上角右下角没有),WJ可以快速奔跑,只是需要拐弯时令人很不爽。为了保持心情愉悦,WJ想知道最少需要几次转弯。

输入

第一行两个数r,c表示地图大小
接下来r行,每行c个字符,‘*’代表此处有障碍,‘0’代表空地。

输出

一个数,表示最少需要几次转弯。数据保证有解。

思路

这题的基础是广度优先搜索,但和普通的略有不同
每一个节点我们都让他向四周扩展,扩展的节点的转弯数为头节点+1(起始为-1),一直扩展到遇到障碍或当前节点已被扩展为止

]]>