CCC '20 S2 - Escape Room (Hard) - DMOJ: Modern Online Judge

CCC '20 S2 - Escape Room (Hard)

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 3.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

C++

You have to determine if it is possible to escape from a room. The room is an $M$ ~M~-by- $N$ ~N~ grid with each position (cell) containing a positive integer. The rows are numbered $1, 2, \dots, M$ ~1, 2, \dots, M~ and the columns are numbered $1, 2, \dots, N$ ~1, 2, \dots, N~. We use $(r,c)$ ~(r,c)~ to refer to the cell in row $r$ ~r~ and column $c$ ~c~.

You start in the top-left corner at $(1,1)$ ~(1,1)~ and exit from the bottom-right corner at $(M,N)$ ~(M,N)~. If you are in a cell containing the value $x$ ~x~, then you can jump to any cell $(a,b)$ ~(a,b)~ satisfying $a \times b = x$ ~a \times b = x~. For example, if you are in a cell containing a $6$ ~6~, you can jump to cell $(2,3)$ ~(2,3)~.

Note that from a cell containing a $6$ ~6~, there are up to four cells you can jump to: $(2,3)$ ~(2,3)~, $(3,2)$ ~(3,2)~, $(1,6)$ ~(1,6)~, or $(6,1)$ ~(6,1)~. If the room is a $5$ ~5~-by- $6$ ~6~ grid, there isn't a row $6$ ~6~ so only the first three jumps would be possible.

Note: The constraints and data have changed from the original problem.

Implementation details

You should implement the following procedure:

bool can_escape(int M, int N, std::vector<std::vector<int>> v)

$M$ ~M~: the number of rows in the room.
$N$ ~N~: the number of columns in the room.
$v$ ~v~: a two-dimensional array of integers representing the values of the cells.
This procedure should return true if it is possible to escape, and false otherwise.

Example

Consider the following call.

can_escape(3, 4, {{0, 0, 0, 0, 0},
                  {0, 3, 10, 8, 1},
                  {0, 1, 11, 12, 12},
                  {0, 6, 2, 3, 9}})

Starting in the cell at $(1,1)$ ~(1,1)~ which contains a $3$ ~3~, one possibility is to jump to the cell at $(1,3)$ ~(1,3)~. This cell contains an $8$ ~8~ so from it, you could jump to the cell at $(2,4)$ ~(2,4)~. This brings you to a cell containing $12$ ~12~ from which you can jump to the exit at $(3,4)$ ~(3,4)~. Note that another way to escape is to jump from the starting cell to the cell at $(3,1)$ ~(3,1)~ to the cell at $(2,3)$ ~(2,3)~ to the exit.

This call should return true.

Constraints

For all subtasks:

$2 \le M,N \le 4\,000$ ~2 \le M,N \le 4\,000~

$v$ ~v~ is an $M+1$ ~M+1~ by $N+1$ ~N+1~ array.

The first row and column of $v$ ~v~ consists of $0$ ~0~'s. The remaining integers are between $1$ ~1~ and $M \times N$ ~M \times N~, inclusive.

Subtask 1 [20%]

$M,N \le 1\,000$ ~M,N \le 1\,000~

Subtask 2 [30%]

$M,N \le 2\,000$ ~M,N \le 2\,000~

Subtask 3 [30%]

$M,N \le 3\,000$ ~M,N \le 3\,000~

Subtask 4 [20%]

No additional constraints.

Comments

5

KevinLyu1006 commented on Jan. 15, 2021, 12:08 p.m.

How large can the integers be in the grid?

5

samliu12 commented on Jan. 15, 2021, 1:39 p.m.

The remaining integers are between 1 and 𝑀×𝑁, inclusive.

2

noYou commented on May 18, 2020, 10:47 p.m.

Why is only C++ allowed?

15

d commented on May 19, 2020, 12:39 a.m.

dmoj has good support for C++ sig grading. I don't want other people to worry about input speed.

7

noYou commented on May 20, 2020, 12:20 a.m.

Guess I have to learn a real language then.

8

Dan13llljws commented on May 18, 2020, 10:59 p.m. ← edited →

std::vector<std::vector<int>> v other languages might be too slow for this problem and sig graders only support c++ (that's what i heard).