Problem A: Laurel Creek
Laurel Creek is a perilous river that divides the campus into two
halves and contains dangerous inhabitants such as geese and beavers.
Your task in this problem is to find a way to cross the river without
getting wet.
To do so, you will take advantage of several tree stumps in
the middle of the river. A tree stump provides a safe place for you to
stand as you ponder your next move. To get from one stump to another,
you walk along logs that connect the stumps.
In cases where no log connects to the stump you wish to reach, all is
not lost. You may pick up any log adjacent to the stump on which you are
standing and put it down somewhere else so that it leads to the stump
you wish to reach. In order for a log to be considered adjacent to a
stump, it must be oriented in the appropriate direction; for example
the log in S-S is adjacent to the two stumps, but the log
in S|S is not considered adjacent to the two stumps.
Each tree stump is located at a point on a square grid. Two stumps
are designated as the beginning and end point of the crossing. Any two
stumps lying in the same row or column of the grid may be connected
by a log. At any point in time, you may perform one of the following
legal moves:
- Traverse a log adjacent to the tree stump you are standing on
to the tree stump at the opposite end of the log.
- Pick up a log adjacent to the tree stump you are standing on.
You may not hold more than one log at a time.
- Put down the log that you are holding so that it connects
the stump you are standing on to some other stump. The log must
be of precisely the right length to reach the other stump.
The log must rest in the water: you may not use a log to connect
two stumps if there is a third stump directly between them,
or if the log would cross some other log already in the water.
Input Specification
The first line of input contains one integer specifying the number of
test cases to follow. Each test case begins with a line containing
two integers 1 <= r <= 15 and 1 <= c <=
15 specifying the number of rows and columns in the grid. Each of
the next r lines of input contains c characters with
the following meaning. The character S denotes a stump. The
characters B and E denote the beginning and end stumps
of the crossing, respectively.
A consecutive sequence of - or |
characters in a line denotes a single log
whose length is proportional to the number
of symbols.
The
character . denotes an empty grid point containing only water.
There will never be more than fifteen stumps in the river.
Sample Input
1
7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E
Output Specification
For each test case, output a line containing a single integer, the
minimum number of moves in which the end stump can be reached from the
initial configuration. If it is not possible to reach the end stump from
the initial configuration, output a line containing the integer 0.
Output for Sample Input
10
Ondřej Lhoták
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.