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.

.

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.

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.

1
7 11
....S......
....|......
B---S......
...........
...........
...........
....S.S...E

10

University of Waterloo Local Contest 2008.09