Escape Room (Hard)

View as PDF

Submit solution

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-by-N grid with each position (cell) containing a positive integer. The rows are numbered 1,2,\dots,M and the columns are numbered 1,2,\dots,N. We use (r,c) to refer to the cell in row r and column c.

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

Note that from a cell containing a 6, there are up to four cells you can jump to: (2,3), (3,2), (1,6), or (6,1). If the room is a 5-by-6 grid, there isn't a row 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: the number of rows in the room.
  • N: the number of columns in the room.
  • 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) which contains a 3, one possibility is to jump to the cell at (1,3). This cell contains an 8 so from it, you could jump to the cell at (2,4). This brings you to a cell containing 12 from which you can jump to the exit at (3,4). Note that another way to escape is to jump from the starting cell to the cell at (3,1) to the cell at (2,3) to the exit.

This call should return true.

Constraints

  • 2 \le M,N \le 4\,000
  • v is a M+1 by N+1 array.
  • The first row and column of v consists of 0's. The remaining integers are between 1 and M \times N, inclusive.

Subtasks

  1. (20 points) M,N \le 1\,000
  2. (30 points) M,N \le 2\,000
  3. (30 points) M,N \le 3\,000
  4. (20 points) No additional constraints

Comments


  • 2
    noYou  commented on May 21, 2020, 8:53 p.m. edited

    if the Integers are between 1 and M x N why is 14 in the sample when M x N = 12?

    EDIT: It has been fixed.


  • 14
    Plasmatic  commented on May 19, 2020, 3:29 p.m.

    can the square brackets be replaced with curly brackets so that the function call can be directly copied?


  • -2
    noYou  commented on May 18, 2020, 6:47 p.m.

    Why is only C++ allowed?


    • 8
      d  commented on May 18, 2020, 8:39 p.m.

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


      • 0
        noYou  commented on May 19, 2020, 8:20 p.m.

        Guess I have to learn a real language then.


    • 3
      Dan13llljws  commented on May 18, 2020, 6: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).