## CCC '20 S2 - Escape Room (Hard)

View as PDF

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 -by- grid with each position (cell) containing a positive integer. The rows are numbered and the columns are numbered . We use to refer to the cell in row and column .

You start in the top-left corner at and exit from the bottom-right corner at . If you are in a cell containing the value , then you can jump to any cell satisfying . For example, if you are in a cell containing a , you can jump to cell .

Note that from a cell containing a , there are up to four cells you can jump to: , , , or . If the room is a -by- grid, there isn't a row 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)

• : the number of rows in the room.
• : the number of columns in the room.
• : 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 which contains a , one possibility is to jump to the cell at . This cell contains an so from it, you could jump to the cell at . This brings you to a cell containing from which you can jump to the exit at . Note that another way to escape is to jump from the starting cell to the cell at to the cell at to the exit.

This call should return true.

#### Constraints

is an by array.

The first row and column of consists of 's. The remaining integers are between and , inclusive.

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

How large can the integers be in the grid?

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

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

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

Why is only C++ allowed?

• 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.

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

Guess I have to learn a real language then.

• 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).