CodePSU 2019 - Advanced

Start

2019-03-24 09:15 AKDT

CodePSU 2019 - Advanced

End

2019-03-24 13:15 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -671 days 3:35:08

Time elapsed

4:00:00

Time remaining

0:00:00

Problem C
Climbers Conundrum

Your friend Madeline is starting a company specializing in giving rock climbing tours to vacationing tourists and nostalgic alumni. While she is a skilled climber, she faces a serious problem in setting up her new pursuit: figuring out which routes up the mountain would be suitable for beginners to climb. The mountain is simply too big for her to try climbing every possible route to determine which routes are best, so she would prefer to rule out any paths that are simply impossible for a beginner to traverse.

Luckily for her, you and your team at the Adventurously Computational Mountaineers have been able to analyze each of the faces of the mountain to create a detailed map of suitable handholds and footholds for beginners to use. In order to make the processing easier, each rock face is broken into square blocks and then each block is individually analyzed determine its climbability. Madeline judges that beginning climbers would only be able to use handholds that lay within one block of the footholds that they are using and that the blocks containing the handholds must be no lower than the blocks containing the footholds that the climbers are using (i.e. if a given climber has their feet set in block $[3, 3]$ then the climbers hands must be in blocks $[2, 3], [3, 3], [4, 3], [2, 4], [3, 4]$, or $[4, 4]$). Additionally, beginning climbers should not need to execute any sort of jumping maneuvers that would require both their hands and their feet to leave the wall simultaneously (i.e. climbers can only move either their hands or their feet at a given time).

Can you help Madeline figure out which faces are climbable?

Input

Each test case consists of one or more rock faces for analysis. The first line of input consists of one integer $t$ ($ 1 \leq t \leq 10$), the number of rock faces in each test. Each rock face begins with a single line of two integers $m$ and $n$ ( $3 \leq m, n \leq 100$ ). The next $m$ lines each contain $n$ characters. Each of these lines corresponds to a row of blocks in decreasing height (i.e. the first row of characters is height $n-1$, the second row of input is height $n-2$, etc). The characters are one of the following:

  • $X$ - This block has neither suitable handholds nor suitable footholds

  • $F$ - This block has suitable footholds, but not suitable handholds

  • $H$ - This block has suitable handholds, but not suitable footholds

  • $B$ - This block contains both suitable handholds and footholds

  • $*$ - The starting location of a climber’s hands and feet on a given rock face (contains suitable handholds and footholds)

    The $*$ for a given rock face is guaranteed to be in the last row of input at height $0$.

Output

For each rock face, output “Climbable” if it is possible for a beginner to climb a rock face so that their hands can reach above the top row (regardless of x-coordinate), or “Not Climbable” if no such path exists.

Sample Input 1 Sample Output 1
1
5 5
FHXXX
XFHXX
XXFHX
XXXFH
XXXX*
Climbable
Sample Input 2 Sample Output 2
2
3 4
HFXX
HFXX
XFH*
3 5
HFXXX
HFFFX
XFXH*
Climbable
Not Climbable