2963: 梦中逃离
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：0
题目描述
机房的训练实在太累了，以至于小y中午趴在桌上做起了白日梦。他梦到自己被困在一个迷宫的左上角（悲惨啊，是不是做这种题目做怕了~），幸好隔壁的小x同学送给他一张迷宫的地图（怎么梦里还出现了他人,难道考试时经常互相帮助？），小x提醒他：出口就是迷宫的右下角，而且告诉他至少有一条路径可以到达出口。整个地图有些地方会有障碍（保证左上角、右下角没有），小y可以快速奔跑，只是需要拐弯时令人很不爽。为了保持心情愉悦，小y想知道最少需要几次转弯。关键时候，小x从梦中消失了，这时，小y突然在机房里大喊一声：帮帮我啊！出于大家都是学友，于是，请你们编程解救他吧~
输入
第一行两个数r和c，表示地图大小。接下来r行，每行c个字符，‘*’代表此处有障碍，‘0’代表空地。
输出
一行一个数，表示最少需要几次转弯。数据保证有解。
样例输入 复制
2 5
0*000
000*0样例输出 复制
4提示
【数据范围】 对于20%的数据满足：r、c ≤ 10。 对于40%的数据满足：r、c ≤ 100。 对于100%的数据满足：r、c ≤ 500。