The travelling tortoise P22295


Statement
 

pdf   zip

thehtml

Find all the paths that a tortoise can travel from an initial position to a final position. The ground has n × m paving stones, each one with a letter painted on it. The tortoise can only make horizontal and vertical movements, and it cannot pass by the same position twice.

Input

Input begins with n and m, followed by n lines with m letters each. Follow a pair of natural numbers indicating the initial row and column, and a pair of naturals numbers indicating the final row and column. The upper-left corner corresponds to the position (0, 0).

Output

Print all the paths from the initial position to the final position.

Information about the checker

You can print the solutions to this exercise in any order.

Public test cases
  • Input

    2 2
    IG
    BA
    1 0  0 1
    

    Output

    BIG
    BAG
    
  • Input

    3 2
    ab
    de
    ab
    0 0  2 1
    

    Output

    adab
    adeb
    abeb
    abedab
    
  • Input

    1 1
    A
    0 0  0 0
    

    Output

    A
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++