Training Site
Sideways banner

Solving a Maze II

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

Solving a maze

Find your way out of 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. 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########