407014: GYM102687 A Hey Gamers
Description
Download and listen to the problem statement here. It is an MP3 audio file that is 3 minutes and 16 seconds long.
The game is available for playing!
Download the following files:
Then, run the game by entering java -jar Pipes.jar in the command line/terminal. Read README.pdf for additional info.
InputThe first line of input contains $$$t$$$, the number of test cases.
The first line of each test case contains two space-separated integers $$$r$$$ and $$$c$$$, the number of rows and the number of columns in the grid.
Each of the next $$$r$$$ lines consist of a string of $$$c$$$ characters, representing the grid. Each character is either:
- a lowercase or uppercase letter,
- '|' which represents a vertical pipe, or
- '-' which represents a horizontal pipe.
For each test case, output one line containing the answer:
- If it is not possible to connect the pairs of letters through a sequence of clicks, output F.
- If it is possible, output the minimum number of clicks needed to connect all pairs of letters.
For all subtasks
$$$1 \le t \le 10$$$
$$$1 \le r, c \le 500$$$
There is exactly zero or two of each letter.
There is at least one letter in the grid.
Subtask 1 (20 points):
$$$1 \le r, c \le 50$$$
The grid contains exactly one pair of equal letters.
Subtask 2 (25 points):
The grid contains exactly one pair of equal letters.
Subtask 3 (30 points):
$$$1 \le r, c \le 50$$$
Subtask 4 (25 points):
No additional constraints.
ExamplesInput2 3 6 -|-|-| |g|-g- -|-|-| 2 2 I| |IOutput
1 FInput
3 4 5 A|-A| -|B|a |---a ||B-| 3 8 |--|---| -A||B|AB |||----| 3 4 |--| BCCB ||--Output
2 F FInput
4 3 10 A--------A x--X--x--X E--------E 2 3 lol |o| 1 4 AbbA 5 8 -||-bW-W a||a--|| Z|Zxbw|w z-zx-|-| r|-||-|rOutput
F F F 9Note
The first sample I/O is valid for all subtasks, while the second and third sample I/O are only valid for the third and fourth subtasks.
The following illustrates the first test case in the second sample I/O:
The minimum number of moves is $$$2$$$, as illustrated by the following:
The following images illustrate the rest of the test cases in the second sample I/O:
It is impossible to connect the letters in both cases, so the output is F for both.