题目描述

一堆“#”迷失在了由“*”组成的二维迷宫中，这个迷宫只有一个出口，这个出口是“0”，“#”们只有从当前位置走到“0”处才能逃离迷宫（“#”可以重叠在同一个位置）。现在输入一个m行n列的迷宫，请你计算出各个“#”逃离迷宫所需要的最短步数。

输入格式

输入m+1行，第一行两个整数n和m，后面输入一个m行n列的矩阵，表示迷宫（m,n<100）

输出格式

输出若干个数字，按照位置从上到下，从左到右的顺序，输出每个“#”逃离迷宫所需要的步数，每行一个数字。

样例

输入#1

5  5
****#
#**#*
**#*0
**#*#
#**##

输出#1

2
5
2
2
3
1
6
3
2

数据范围/约定

时间空间限制：1s, 256MB.