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?
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$.
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 |