← 返回题目列表

AtCoder · abc427_e

E. 风清洁

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

分数: 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