AT_abc427_e.[ABC427E] Wind Cleaning

有一个 $H$ 行 $W$ 列的网格。设 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

高桥位于这个网格中的某个格子，网格中有些格子上有垃圾。

每个格子的状态由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 给出，其中 $S_{i, j}$ 表示 $S_i$ 的第 $j$ 个字符，含义如下：

• 如果 $S_{i, j} =$ T，那么 $(i, j)$ 格子是高桥所在的位置；
• 如果 $S_{i, j} =$ #，那么 $(i, j)$ 格子上有垃圾；
• 如果 $S_{i, j} =$ .，那么 $(i, j)$ 格子为空，没有垃圾。

高桥所在的格子上没有垃圾。

他可以重复执行如下操作：

• 选择四个方向之一（上、下、左、右），并将所有垃圾同时向该方向移动一格。若垃圾移出网格，则该垃圾会消失；若垃圾移到他所在的格子，他就会变脏。

请判断，能否在不让他变脏的情况下，让所有垃圾都消失。如果可以，输出所需的最小操作次数；否则输出 $-1$。

输入按以下格式从标准输入读入：

$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$

如果高桥可以在不变脏的情况下让所有垃圾都消失，输出最小操作次数。否则输出 $-1$。

样例解释 1

高桥可以用三次操作使所有垃圾消失，过程如下：

• 第一次选择“上”，操作后垃圾位于 $(1, 1)$ 和 $(2, 4)$。
• 第二次选择“右”，操作后垃圾位于 $(1, 2)$。
• 第三次选择“上”，操作后所有垃圾消失。

数据范围

• $2 \leq H, W \leq 12$
• $S_i$ 为长度为 $W$ 的只包含 T、# 和 . 的字符串
• 恰有一个 $(i, j)$ 使 $S_{i, j} =$ T
• 至少有一个 $(i, j)$ 使 $S_{i, j} =$ #

由 ChatGPT 5 翻译