Path Finder 2: Electric Boogaloo

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

You are given an N×M grid with K blocked squares and the others open. From an open square, you may move to any other open square that shares an edge with your current square. For Q queries of 4 integers r_a, c_a, r_b, c_b, please determine whether there is a path from (r_a, c_a) to (r_b, c_b).

Constraints

For all subtasks:

1 \le N, M, Q \le 5 \times 10^5

0 \le K \le 5 \times 10^5

1 \le r_i, r_a, r_b \le N

1 \le c_i, c_a, c_b \le M

Each given blocked square is unique, and for all queries the squares (r_a, c_a) and (r_b, c_b) will not be blocked.

Subtask 1 [20%]

1 \le N, M \le 2 \times 10^3

Subtask 2 [80%]

No further constraints.

Input Specification

The first line will contain 4 integers N, M, K, and Q.

The next K lines will each contain 2 integers r_i and c_i, representing that square (r_i, c_i) is blocked.

The following Q lines will each contain 4 integers r_a, c_a, r_b, c_b, representing a query from (r_a, c_a) to (r_b, c_b).

Output Specification

For each query, output one line containing YES if it is possible to reach (r_b, c_b) from (r_a, c_a), or NO otherwise.

Sample Input 1

5 5 11 1
2 2
4 2
3 2
2 3
5 2
3 1
1 5
3 5
2 5
4 5
4 4
1 1 5 5

Sample Output 1

YES

Explanation for Sample 1

The following is a diagram for the grid given in Sample 1 (. marks open squares, while # marks blocked squares):

....#
.##.#
##..#
.#.##
.#...

It can be shown that there is a path from (1, 1) to (5, 5) in the grid above.

Sample Input 2

5 5 9 3
5 1
1 2
1 5
3 2
2 3
5 3
3 3
3 5
4 4
1 1 5 5
2 1 4 3
2 5 2 5

Sample Output 2

NO
YES
YES

Explanation for Sample 2

The following is a diagram for the grid given in Sample 2 (. marks open squares, while # marks blocked squares):

.#..#
..#..
.##.#
...#.
#.#..

Comments

There are no comments at the moment.