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)