Consider a square grid with lamps in fixed locations. Each lamp can either illuminate its row or its column, but not both. The illumination of each lamp extends over a limited distance.

Any square in the grid should only be illuminated by at most one lamp in its row and by at most one lamp in its column (one of each is acceptable, as is just the row, just the column, or neither). Determine if it is possible for all lamps to be lit while satisfying these constraints.


Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains three positive integers, $n$, $r$ and $k$ ($1 \le n, r, k \le 1\, 000, k \le n^2$), where $n$ is the size of one side of the square grid, $r$ is the maximum reach of a lamp, and $k$ is the number of lamps. The next $k$ lines will each contain two positive integers $i$ and $j$ ($1 \le i, j \le n$), indicating that there is a lamp in the grid at row $i$, column $j$.

Each lamp can illuminate squares at most $r$ units away, and can also illuminate its own square, so the maximum number of squares it can illuminate is $2 r + 1$. All lamps will be in distinct locations.


Output a single integer, $1$ if it is possible to light all of the lamps and $0$ if it is not possible.

Sample Input 1 Sample Output 1
3 2 5
1 1
1 3
3 1
3 3
2 2
Sample Input 2 Sample Output 2
3 2 6
1 1
1 2
1 3
3 1
3 2
3 3
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 3.4medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in