分数: 400 分
问题陈述
高桥被困在一栋老建筑内的迷宫中。
建筑物表示为一个网格,其中 N 行和 M 列。牢房位于 i从顶部开始的第行和 j从左边算起的第列称为单元格 (i, j)。的状态 i- 网格的第行由字符串表示 S_i:如果 j- 第一个字符 S_i is #,然后是单元格 (i, j) 是一堵墙;如果是的话 .,然后是单元格 (i, j) 是一段。
高桥目前在牢房 (1, 1) 并旨在到达牢房的出口 (N, M) 在右下角。
在一次操作中,高桥可以从当前单元格移动到四个相邻单元格之一(上、下、左或右)。然而,他无法移出网格。如果目标单元格是一个通道,他只需移动到那里即可。如果目标单元格是一堵墙,他会用锤子摧毁墙,将其变成一条通道,然后移动到那里。每破坏一堵墙,破坏数量就会增加 1。被破坏并转化为通道的细胞此后仍然是通道。锤子的使用次数没有限制,移动次数也没有限制。
由于高桥可以根据需要多次破坏墙壁,因此他总是可以到达牢房 (N, M)。求高桥离开牢房需要摧毁的最少墙壁数量 (1, 1) 到单元格 (N, M).
保证电池 (1, 1) 和细胞 (N, M) 始终是段落。
约束
- 1 \leq N \leq 500
- 1 \leq M \leq 500
- N, M 是整数
- S_i (1 \leq i \leq N) 是一个长度为的字符串 M 组成
#和. - 的
树的 1st 字符 S_1 is
. - 的
树的 M- 第一个字符 S_N is
.
输入
N M S_1 S_2 \vdots S_N
- 第一行包含行数 N 和列数 网格的 M ,以空格分隔。
- 的
树的 (1 + i)第行 (1 \leq i \leq N) 包含一个字符串 S_i 长度 M 代表的状态 i- 网格的第行。的 j- 第一个字符 S_i 代表cell的状态 (i, j),其中
#指一堵墙,并且.表示一段。
输出
在一行中打印出高桥从牢房出发需要摧毁的最少墙壁数量 (1, 1) 到单元格 (N, M).
示例输入 1
3 5 ...#. .###. ...#.
示例输出 1
1
示例输入 2
3 3 ... ... ...
示例输出 2
0
示例输入 3
5 7 ..#.#.# .#...#. ##.#.## .#...#. ..#.#..
示例输出 3
2
示例输入 4
10 10 .......... .########. .......... .########. .......... .########. .......... .########. .......... ..........
示例输出 4
0
示例输入 5
1 1 .
示例输出 5
0
示例输入 6
3 5 ...#. .###. ...#.
示例输出 6
1
示例输入 7
3 3 ... ... ...
示例输出 7
0
示例输入 8
5 7 .#.#.#. .#.#.#. .#.#.#. .#.#.#. .......
示例输出 8
0
示例输入 9
10 10 .......... .########. .......... ########.# .......... .########. .......... ########.# .......... ..........
示例输出 9
0
示例输入 10
1 1 .
示例输出 10
0