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 ith 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)

Getting a TLE. Can someone tell me what is wrong, my approach or my code?

Your approach is likely correct but too slow and unnecessarily complicated. Here's a hint, 4.

Can the farmer have more than 1 farm?

No, the farmer only has one farm.