Author: | A. Baranov | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
You are given a board of n×m cells, one of them is occupied by a chess knight. Some cells were removed from the board.
Your program must determine the minimal number of moves that a knight must perform to visit all cells of a given list in order, not visiting removed cells in the process.
On other words, given list of cells must be a subsequence of cells visited by the knight.
Input file contains integers n and m — board size.
Next there is an integer P, followed by P pairs of integers (ai,bi) — coordinated of removed cells.
Next there is an integer L, followed by L pairs of integers (xi,yi) — coordinates of cells to visit (starting with initial position of the knight).
Output file must contain a single integer — minimal number of moves.
If there is no solution, output −1.
0<|xi+1−xi|+|yi+1−yi|, 2≤(n,m)≤100,
0≤(ai,xi)<n, 0≤(bi,yi)<m,
0≤P≤5000, 2≤L≤100
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|