Path Finder

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Java 8 2.0s

PyPy 2 2.0s

PyPy 3 2.0s

Memory limit: 512M

Author:

4fecta

Problem type

You are given an $N \times M$ $N \times M$ grid with $K$ $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)$ $(1, 1)$ to $(N, M)$ $(N, M)$ .

Constraints

For all subtasks:

$2 \le N, M \le 5 \times 10^5$ $2 \leq N, M \leq 5 \times 10^{5}$

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

$1 \le r_i \le N$ $1 \leq r_{i} \leq N$

$1 \le c_i \le M$ $1 \leq c_{i} \leq M$

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

Subtask 1 [15%]

$2 \le N, M \le 2 \times 10^3$ $2 \leq N, M \leq 2 \times 10^{3}$

Subtask 2 [85%]

No additional constraints.

Input Specification

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

The next $K$ $K$ lines will each contain $2$ $2$ integers $r_i$ $r_{i}$ and $c_i$ $c_{i}$ , representing that square $(r_i, c_i)$ $(r_{i}, c_{i})$ is blocked.

Output Specification

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

Sample Input 1

Copy

Sample Output 1

Copy

YES

Explanation for Sample 1

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

Copy

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

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

Sample Input 2

Copy

Sample Output 2

Copy

NO

Explanation for Sample 2

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

Copy

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

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

Comments

-4

John commented on May 3, 2022, 6:02 p.m.

"Let's have fun, friend!"

-7

KayinM commented on May 5, 2022, 1:24 p.m. ← edited →

Ratio + Apex sucks!!

This comment is hidden due to too much negative feedback. Show it anyway.

-3

John commented on May 5, 2022, 6:03 p.m.

I bet you're a fortnite player

-6

Evan2019 commented on May 5, 2022, 1:24 p.m.

"Oh no, ~~someone's shooting at us~~ we're failing this problem!"

This comment is hidden due to too much negative feedback. Show it anyway.

-3

Daniel_Alp commented on May 3, 2022, 3:10 a.m. ← edited →

After swapping from Scanner to BufferedReader, my submission gets the java.util.NoSuchElementException. I am may be incorrectly using the BufferedReader (I am using the code provided at https://dmoj.ca/tips/), or if I have a mistake somewhere else in the program. I have read about this error on Oracle, but am still unable to figure out why it is happening, and cannot replicate the error in my program on IntelliJ. Any suggestion as to which sources I should read / or any test cases to try would help. Thank you! Edit: I fixed all the bugs and holy moly there were a LOT.

-4

1jiangand2 commented on May 3, 2022, 1:08 p.m.

I believe you need to make a new String Tokenizer for each line of input, if you haven't done that already.