← 返回题目列表

AtCoder · arc214_f

F. 不可预测的举动

中文机器翻译题面 查看原题

分数: 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) 不破坏任何壁细胞。