Path Finder

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Java 8 2.0s
PyPy 2 2.0s
PyPy 3 2.0s
Memory limit: 512M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are given an N \times 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. Please find out whether there is a path from (1, 1) to (N, M).

Input Specification

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

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

Output Specification

Output one line containing YES if it is possible to reach (N, M) from (1, 1), or NO otherwise.

Constraints

2 \le N, M \le 5 \times 10^5

0 \le K \le \min(5 \times 10^5, N \times M - 2)

1 \le r_i \le N

1 \le c_i \le M

Each given blocked square is unique, and the squares (1, 1) and (N, M) will not be blocked.

Subtask 1 [15%]

2 \le N, M \le 2000

Subtask 2 [85%]

No further constraints.

Sample Input 1

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

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
5 1
1 2
1 5
3 2
2 3
5 3
3 3
3 5
4 4

Sample Output 2

NO

Explanation for Sample 2

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

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

It can be shown that there are no paths from (1, 1) to (5, 5) in the grid above.


Comments

There are no comments at the moment.