Trial of Doom
All submissions for this problem are available.
Johnny has reached the final trial on the Path of Doom. This is the hardest one. He entered a large room. The floor of the room is divided into square cells of the same size. There are n rows and m columns of cells. Each cell can be either red or blue. We can consider that the walls of the room are parallel south-north direction and west-east direction and that Johnny has entered the room in the north-western corner. So now he is standing in the north-western cell of the room. The exit is in the south-eastern corner. Johnny can make steps in each of the eight directions moving to adjacent cells. He has to reach the exit. But when he goes out of the room all the cells in the room should be blue, otherwise he fails the trial (If Johnny goes out he can't step back again). The colors of the cells change after each step Johnny makes. When he steps on the next cell this cell and the cells to its north, south, east and west change color: from blue to red and from red to blue. Johnny can't ever step on two cells at once or he fails the trial. Also just jumping on the cell he is standing on now will have no effect on the color of cells. Currently some cells in the room may be red. Johnny made a look over the room and he wonders if it's even possible to pass the trial at all or the trial master is playing a trick on him. Help him find this out.
The first line of input is the number of test cases. Then each of the test cases follows. The test case starts with two number n and m - the sizes of the room. The next line contains number k - the amount of red cells in the room. Next k lines consist of two numbers each x, y - the row number and column number of the following red cell. The rows are numbered from 1 to n from north to south and columns are numbered from 1 to m from west to east. So Johnny starts at cell (1, 1) and have to reach cell (n, m). The coordinates of all of the red cells will be different. The rest of the cells are blue.
1 <= t <= 50
1 <= n, m <= 109
min(n, m) < 40
0 <= k <= min(m*n, 10000)
1 <= x <= n
1 <= y <= m
For each test case print "YES" (quotes for clarity) if Johnny can reach the south-eastern cell and go out of the room with all cells being blue and "NO" (quotes for clarity) otherwise.
Input: 3 2 2 0 2 2 4 1 1 1 2 2 1 2 2 4 4 1 1 1 Output: YES YES NO
In the first test case Johnny can pass the trial making the following steps: South-east, North, West, East, West, South-east, out. In the second test case: East, West, South, East, out. It's impossible to pass the trial in the third test case.
|Tags||july11, medium, spooky|
|Time Limit:||1.485 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.