Generalized chess knight P22796


Statement
 

pdf   zip

html

Let us define an (a, b) knight as a piece that moves by jumping a cells in one direction and b cells in the other direction, where the possible directions are horizontal and vertical. For instance, the traditional chess knight is a (1, 2) knight.

Given an n × m board with obstacles, an initial position (i1, j1), a final position (i2, j2), and the pair (a, b), can you tell if an (a, b) knight initially located at (i1, j1) can reach (i2, j2) in two or less steps? The knight can never leave the board, nor visit any obstacles.

Input

Input consists of several cases, each with n and m, followed by the board (n lines with m characters each, where an ‘X’ indicates an obstacle and a ‘.’ indicates a free cell), followed by i1, j1, i2, j2, a and b. Assume that n and m are between 1 and 42, that (i1, j1) and (i2, j2) are free positions inside the board, and 1 ≤ a < b ≤ 5. The upper-left position is (0, 0).

Output

For every case, print “yes” or “no” depending on whether the goal position is reachable from the initial position in two or less steps.

Public test cases
  • Input

    2 3
    ...
    ...
    0 0  1 2  1 2
    
    4 5
    .....
    XXXXX
    XXXXX
    .....
    0 1  3 0  1 3
    
    5 5
    .XXX.
    XXXXX
    XXXXX
    XXXXX
    XX.XX
    0 4  0 0  2 4
    
    5 5
    .XXX.
    XXXXX
    XXXXX
    XXXXX
    XXXXX
    0 4  0 0  2 4
    
    1 8
    XXXXXXX.
    0 7  0 7  3 5
    

    Output

    yes
    yes
    yes
    no
    yes
    
  • Information
    Author
    Enric Cusell
    Language
    English
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++
    Event
    Dotzè Concurs de Programació de la UPC - Final
    Date
    2014-10-01