分数: 900 点
问题陈述
有一个 H \times W 网格。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
每个单元格都是空单元格或壁单元格,该信息由下式表示 H \times W 字符 S_{1,1},\dots ,S_{H,W}。
细胞 (i,j) 是一个空单元格,如果 S_{i,j} is .,以及壁细胞(如果是) #.
最初,高桥在牢房里 (1,1)。 他可以沿四个方向(上、下、左、右)之一移动到与当前单元格相邻的单元格任意次数。 然而, 他不能连续两次向同一方向移动。 此外,他无法移动到墙壁牢房或网格之外。
在开始移动之前,他可以摧毁零个或多个墙壁单元,将它们变成空单元。 他需要破坏多少个壁细胞才能到达细胞 (H,W)? 在这个问题的约束下,可以证明存在一种方法可以破坏壁细胞,使他能够到达细胞 (H,W).
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \le T \le 1000
- 2 \le H, W \le 100
- S_{i,j} is
.or#. - S_{1,1} 和 S_{H,W} 是
.. - 总和 HW 所有测试用例最多 3 \times 10^4.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}
输出
输出 T 行。
的 i-th 行应包含尽可能少数量的壁细胞,以便 Takahashi 到达细胞 (H,W) 为 i- 第一个测试用例。
示例输入 1
3 3 5 ..##. .#... ##.#. 2 3 ..# #.. 13 13 .############ ##.##..###..# #.#.#.#.#.### #...#..##.### #.#.#.#.#.### #.#.#.#.##..# ############# #...##.##.#.# ###.#..##.#.# #...##.##...# #.####.####.# #...#...###.# ############.
示例输出 1
2 0 13
对于第一个测试用例,Takahashi 可以到达单元格 (H,W) 通过破坏两个壁细胞,如下所示。

左侧显示了要破坏的壁细胞的示例,右侧显示了移动路径的示例。 请注意,没有必要最小化移动次数,并且允许多次访问同一单元格。
对于第二个测试用例,他可以到达单元格 (H,W) 不破坏任何壁细胞。