0123. (p, q)-Horse
| Input file name: | horse.in |
| Output file name: | horse.out |
| Time limit: | 500 ms |
| Memory limit: | 64 megabytes |
(p,q)-horse is a generalisation of chess Knight who moves p steps one direction and q steps another (perpendicular) direction. Ordinary chess Knight is thus a (2,1)-horse.
Your task is to determine how many moves (p,q)-horse needs to go from one cell on M*N chess-board to another.
Input file
One and only line in the input file contains 8 integer numbers M, N, p, q, x1, y1, x2, y2 (1 ≤ x1, x2 ≤ M, 1 ≤ y1, y2 ≤ N, 0 ≤ p ≤ M ≤ 100, 0 ≤ q ≤ N ≤ 100).
Output file
First line of the output file must contain an integer number k – number of moves that (p,q)-horse needs to move from cell (x1,y1) to the cell (x2,y2). k+1 lines must follow, containing sequential positions of (p,q)-horse on the way.
If (p,q)-horse cannot reach (x2,y2) from (x1,y1), output -1.
Examples:
| horse.in | horse.out |
|---|---|
| 3 3 1 1 1 1 3 3 | 2 1 1 2 2 3 3 |
| 2 2 1 1 1 1 1 2 | -1 |
Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov
Discuss Submit a solution