### University of Toronto ACM-ICPC Tryouts 2012

## D: Reverse Fox Hunt

A family of Foxen, having caught a pesky farmer on their property, want to teach him a lesson. Of course, they're not cruel - they plan to simply prevent him from returning home to his farm, until he's willing to beg them for mercy.

The Foxen and the farmer live in a forest, which may be viewed as a grid of cells, with `H` (1 ≤ `H` ≤ 6) rows of `W` (1 ≤ `W` ≤ 6) cells each. Each cell contains either grass (represented by "G"), trees ("T"), the farmer ("F"), or his farm ("H"). The farmer may repeatedly move up, down, left, or right to adjacent cells within the grid, provided that they are not blocked by trees. Due to his overconfidence in exploring the forest, the farmer is not directly adjacent to his farm.

The family of Foxen can also block the farmer's way, by standing in grass-filled cells. He would not, of course, dare to enter a cell with a Fox in it. However, the Foxen do have better things to do, so they'd like to determine the minimum number of cells they must occupy in order to prevent the farmer from ever reaching his farm.

There are `T` (1 ≤ `T` ≤ 20) scenarios as described above. For each one, you'd like to answer the Foxen's question. Note that no Foxen might be necessary, if the trees already bar the farmer's way sufficiently.

### Input

Line 1: 1 integer, `T`

For each scenario:

Line 1: 2 integers, `H` and `W`

Next `H` lines: `W` characters, representing the `i`th row of the grid, for `i` = 1..`H`

### Output

For each scenario:

Line 1: 1 integer, the minimum number of Foxen necessary to block the farmer.

### Sample Input

2 1 5 FGTGH 4 5 GGGGG GFGTG GTTGH GGGGG

### Sample Output

0 2

### Explanation of Sample

In the first scenario, the farmer can already never reach his farm, so no Foxen are necessary.

In the second scenario, one possible placement of two Foxen (each represented by an "X") is as follows:

GGGGX GFGTG GTTGH GGXGG

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 15.00s

**Memory Limit:** 64M

**Added:** Oct 02, 2012

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

tejask06on Jun 23, 2015 - 12:36:55 pm UTC TLEwgma00on Jun 23, 2015 - 10:00:02 pm UTC Re: TLEkobortoron Mar 28, 2015 - 3:37:52 am UTC Farmswgma00on Mar 28, 2015 - 9:52:23 am UTC Re: Farms