Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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 letter E stands for an exit, and the capital letter 'S' stands 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 the S 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########