After the Dance Battle¶
Walking home in triumph after a particularly satisfying dance battle, you take a wrong turn into an alley and find yourself presented with a perplexing puzzle. The entrance to the alley behind you disappears and you are faced with a rectangular grid of colorful squares, with thick granite walls occupying some of the squares. The grid is recessed far enough into the ground that, from above, you can see the exit in the distance and the layout of all the colors. You can memorize the entire layout before entering the grid and trying to make your way across.
As you stand above the grid trying to commit its layout to memory, you notice something strange about the urban wildlife trapped with you in the maze; the various fauna seem to be able to move almost instantaneously between squares of the same color. You suspect that you can use this property to your advantage, which you attempt to keep at the front of your mind as you enter the labyrinth with your intentions set on getting out as quickly as possible.
Input¶
Your input file will consist of a number N followed by some whitespace and then N test cases. Each case consists of two numbers R and C, the number of rows and columns in the maze, followed by R strings describing the layout of the rows in order. All tokens are whitespace-separated.
Each element describing a row will consist of the characters ‘S’, ‘E’, ‘W’, or the digits 0-9. There will be only one ‘S’ square and one ‘E’ square, ‘S’ being your starting point and ‘E’ being the exit. ‘S’ will be in the first row, ‘E’ will be in the last row. ‘W’ squares are occupied by walls, and cannot be entered. Digits 1-9 represent the colors of the squares. You can pass in a single step between adjacent squares or between any two squares of the same color. The start and exit points as well as all ‘0’ squares are inert, i.e., they have no color and must be stepped directly on to or off of. There will always be some valid method of reaching the exit.
Output¶
Return the number of steps required to reach the exit from the starting point.
Example input¶
5
5 3
00S
02W
009
W50
E0W
10 6
000S0W
00000W
000WW0
000WWW
W0400W
0000WW
0300WW
W000WW
0000WW
WE0000
15 9
00W0000S0
0000W0000
0WW000000
00W000000
000050000
000080005
050000000
000000000
W0W00W000
00WW0WW00
WWWW00000
0W0090500
WWW0W0000
WW00WW000
0W0WWE000
20 12
40000000S00W
000000000000
03000000000W
100000008000
000000000000
000000700000
000000000700
000000000000
070000000000
000000002070
000100000000
000000000430
000000000000
000004004000
350000000000
W02010000030
W10000000000
000100000300
000009000000
0E0000005000
25 15
0WS00W0W600WWW0
0W6W00WWW0WW0W0
WW0W00W0WW0WWWW
W0WW04WWWW0WW0W
WW0W0000WWWWWW0
000WWW000WWW9W0
W0WWWW00000WWW0
0WWW0WW0W00WW90
WWW000WW0000WWW
W0W000WW0000WWW
0W0800WW0W00000
W000W0W4WW00WWW
000000WW00000WW
W000030000304W0
W00000W0000000W
W08000000000000
WW00WW00W0W0400
000W0W00300W050
00WWWWWW0WWWW40
00WWWWWWWW00WW0
00WW0000W000WW0
000000000000WWW
W602000000W05W0
090000000000W0W
WWWWWW000000EW0