## Path Finder 2: Electric Boogaloo

View as PDF

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

Authors:
Problem type

You are given an grid with 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 queries of integers , please determine whether there is a path from to .

#### Constraints

Each given blocked square is unique, and for all queries the squares and will not be blocked.

#### Input Specification

The first line will contain integers , , , and .

The next lines will each contain integers and , representing that square is blocked.

The following lines will each contain integers , representing a query from to .

#### Output Specification

For each query, output one line containing YES if it is possible to reach from , 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 to 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):

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