CEN303 2013-15 Questions |
Start: Dec.15.2013 at 02:00:00 PM
Finish: Dec.15.2013 at 07:00:00 PM
The contest is finished!
• Contest scoreboard
|
Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
The Knight Move
In chess the knight has 8 possible moves. Assume that
you are given only 4 possible moves for it: for a position
(x, y) the possible moves are
(x+2, y+1), (x+1, y-2), (x-1, y+2) and
(x-2, y-1) (refer the image
on the right for orientation).
And assume that this is not a chessboard but an
n x n board. If you are given the
initial (xi, yi)
and final (xf, yf)
positions of it, and if you are
also given m positions which are occupied by other pieces
where the knight cannot move on them.
Question:
Write a program that tries all possible moves
and decides if the knight can move over the
destination (xf, yf)
cell or not.
Input specification
You will be first given 2 numbers
- The size of the board (n) where the board is
an nxn matrice and 1 ≤ n ≤ 100
- The number of cells (m) occupied by other pieces
where 0 ≤ m ≤ 500
Then in the following line you will be given four
integers initial (xi, yi position
of the knight and the position that the knight wants
to reach (xf, yf). Then, in the
following m lines you will be given (x,y) coordinates
of m occupied cells.
Output specification
Show "Yes", if there is a possible path to the destination.
"No", otherwise.
Sample Input I
3 1
1 1 2 2
1 2
|
Sample Input II
4 2
1 1 2 4
4 1
4 2
|
Sample Output I
No
|
Sample Output II
Yes
|
Для отправки решений необходимо выполнить вход.
|