给你一个$n \times m$的矩形,#
表示墙不能通过,S
表示起点(可以通过),.
表示空地。你每次可以沿着上下左右四个方向移动。
问从S
点出发,到达所有点最少需要移动多少次。
输入格式
第一行,两个整数$n,m$。
接下来$n$行,每行一个长度为$m$的字符串。
输出格式
一共$n$行$m$列,每个数表示移动到对应位置需要多少步,如果是墙或者无法到达,输出-1
。
样例输入
5 5
.#.#.
.###.
..S#.
.##..
.....
样例输出
4 -1 -1 -1 12
3 -1 -1 -1 11
2 1 0 -1 10
3 -1 -1 8 9
4 5 6 7 8
数据规模
对于所有数据,保证$1\leq n,m \leq 200$,恰好有一个S
。