Training Site

# Solving a Maze II

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds

# Solving a maze

### Input

On the first line of input there is one integer, N <= 50, giving the number of test cases in the input. Each test case starts with a line containing two integers x, y such that 1 <= x, y <= 50. After this, y lines follow, each with x characters. For each character, a space " stands for an open space, a hash mark#stands for an obstructing wall, the capital letterEstands for an exit, and the capital letterSstands for the start of the search. The perimeter of the maze is always closed, i.e., there is no way to get out from the coordinate of theS" except via an exit

### Output

For every test case, output the maze showing the path to the nearest exit given as digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (modulo 10) etc for each step to the exit – the start is 0 but still display as S. Likewise display the exit as E. Ensure you visit adjacent cells in the order: right, down, left, up - assuming y rows and x columns numbered from the top right corner. Separate the mazes with a blank line (none at the end)

• ### Sample Input 1

2
4 4
####
# S#
#  #
##E#
10 5
##########
#  #  # S#
#        #
#  #  #  #
#E########


### Sample Output 1

####
# S#
# 1#
##E#

##########
#  #  # S#
# 7654321#
#98#  #  #
#E########