分数: 500 点
问题陈述
有一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
高桥位于该网格的其中一个单元格上,并且该网格的某些单元格上有垃圾。
单元格的状态由下式给出 H 字符串 S_1, S_2, \ldots, S_H 长度 W,其中 S_{i, j} 表示 j- 第一个字符 S_i 代表以下状态:
- If S_{i, j} =
T,细胞 (i, j) 是高桥所在的单元格。 - If S_{i, j} =
#,细胞 (i, j) 是一个有垃圾的单元格。 - If S_{i, j} =
.,细胞 (i, j) 是一个没有垃圾的空单元格。
高桥所在的牢房里没有垃圾。
他可以重复执行以下操作:
- 选择四个方向之一(上、下、左或右),然后将所有垃圾同时沿该方向移动一个单元格。在这里,如果垃圾移出网格,垃圾就会消失,如果垃圾移动到他所在的牢房,他就会变脏。
判断他是否有可能在不弄脏的情况下让所有垃圾消失,如果可能,求最少可能的操作次数。
约束
- 2 \leq H, W \leq 12
- S_i 是一个长度为的字符串 W 组成
T,#,和.. - 正好有一个 (i, j) 这样 S_{i, j} =
T. - 至少有一个 (i, j) 这样 S_{i, j} =
#.
输入
输入由标准输入按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
如果高桥可以使所有垃圾消失而不弄脏,请打印尽可能少的操作数。否则,打印 -1.
示例输入 1
3 4 ###. #.T. ...#
示例输出 1
3
高桥可以通过以下三个操作使所有垃圾消失:
-
选择。执行此操作后,细胞上会出现垃圾 (1, 1) 和 (2, 4).
-
选择正确。执行此操作后,单元格上将出现垃圾 (1, 2).
-
选择。执行此操作后,所有垃圾都消失了。
示例输入 2
3 3 ### #T# ###
示例输出 2
-1
示例输入 3
5 5 ###.. #T... ..##. ##..# #..#.
示例输出 3
5