E - Wind Cleaning 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

H 行 W 列のグリッドがあります。このグリッドの上から i 行目、左から j 列目のマスを (i, j) と表記します。

高橋君はこのグリッドの 1 つのマスの上におり、グリッド上のいくつかのマスにはゴミが落ちています。

各マスの状態は 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 つ選び、すべてのゴミを同時にその方向へ 1 マス移動させる。ただし、ゴミがグリッドの外に出た場合にはゴミは消滅し、高橋君のいるマスにゴミが移動した場合は高橋君は汚れる。

高橋君が汚れることなくすべてのゴミを消滅させることができるか判定し、できる場合は操作を行う回数の最小値を求めてください。

制約

  • 2 \leq H, W \leq 12
  • S_i は長さ W の T, #, . からなる文字列
  • S_{i, j} = T なる (i, j) がちょうど 1 つ存在する
  • S_{i, j} = # なる (i, j) が1 つ以上存在する

入力

入力は以下の形式で標準入力から与えられる。

H W
S_1
S_2
\vdots
S_H

出力

高橋君が汚れることなくすべてのゴミを消滅させることができる場合、操作を行う回数として考えられる最小値を出力せよ。そうでないとき、-1 と出力せよ。

入力例 1

3 4
###.
#.T.
...#

出力例 1

3

高橋君は以下のように操作を行うことで 3 回の操作ですべてのゴミを消滅させることができます。

  • 上を選ぶ。この操作後、ゴミはマス (1, 1) とマス (2, 4) にある。

  • 右を選ぶ。この操作後、ゴミはマス (1, 2) にある。

  • 上を選ぶ。この操作後、すべてのゴミは消滅している。

入力例 2

3 3
###
#T#
###

出力例 2

-1

入力例 3

5 5
###..
#T...
..##.
##..#
#..#.

出力例 3

5

Score : 500 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Takahashi is on one of the cells in this grid, and there is trash on some cells of the grid.

The states of the cells are given by H strings S_1, S_2, \ldots, S_H of length W, where S_{i, j} denotes the j-th character of S_i and represents the following state:

  • If S_{i, j} = T, cell (i, j) is the cell where Takahashi is.
  • If S_{i, j} = #, cell (i, j) is a cell with trash.
  • If S_{i, j} = ., cell (i, j) is an empty cell without trash.

There is no trash on the cell where Takahashi is.

He can repeatedly perform the following operation:

  • Choose one of the four directions (up, down, left, or right), and move all trash simultaneously one cell in that direction. Here, if trash goes outside the grid, the trash disappears, and if trash moves to the cell where he is, he gets dirty.

Determine whether it is possible for him to make all trash disappear without getting dirty, and if possible, find the minimum possible number of operations.

Constraints

  • 2 \leq H, W \leq 12
  • S_i is a string of length W consisting of T, #, and ..
  • There is exactly one (i, j) such that S_{i, j} = T.
  • There is at least one (i, j) such that S_{i, j} = #.

Input

The input is given from Standard Input in the following format:

H W
S_1
S_2
\vdots
S_H

Output

If it is possible for Takahashi to make all trash disappear without getting dirty, print the minimum possible number of operations. Otherwise, print -1.

Sample Input 1

3 4
###.
#.T.
...#

Sample Output 1

3

Takahashi can make all trash disappear in three operations as follows:

  • Choose up. After this operation, trash is on cells (1, 1) and (2, 4).

  • Choose right. After this operation, trash is on cell (1, 2).

  • Choose up. After this operation, all trash has disappeared.

Sample Input 2

3 3
###
#T#
###

Sample Output 2

-1

Sample Input 3

5 5
###..
#T...
..##.
##..#
#..#.

Sample Output 3

5