University of Toronto ACM-ICPC Tryouts 2012
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 \le H \le 6)~ rows of ~W~ ~(1 \le W \le 6)~ cells
each. Each cell contains either grass (represented by
G), trees (
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 \le T \le 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.
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 \dots H~
For each scenario:
Line 1: 1 integer, the minimum number of Foxen necessary to block the farmer.
2 1 5 FGTGH 4 5 GGGGG GFGTG GTTGH GGGGG
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