This problem looks like a grid movement problem, but it is not about moving up, down, left, or right. Each cell contains a number, and that number tells us which coordinates we are allowed to jump to.

The clean way to solve the problem is to model the grid as an implicit graph. Each cell is a node, and from a cell with value x, we can jump to every cell (a, b) where a * b = x.

What the Problem Is Asking

We are given an M x N grid. Rows are numbered from 1 to M, and columns are numbered from 1 to N.

We start at (1, 1) and want to reach (M, N).

If the current cell contains x, then we may jump to any valid cell (a, b) such that:

a * b = x

If the target cell is outside the grid, it is not a valid jump.

We output yes if the exit can be reached, and no otherwise.

Where Beginners Often Get Stuck

The first trap is treating this like a normal grid traversal. There are no four-direction moves here.

The second trap is factoring the current value again and again. For example, from a cell with value 12, we may think about factor pairs such as (1, 12), (2, 6), (3, 4), and so on.

That works conceptually, but repeated factor checks can become inefficient. A better approach is to reverse the question:

For each possible product p, which cells have row * column = p?

Core Algorithm Idea

We build an index:

product_to_cells[p] = all cells (r, c) where r * c = p

Then, when BFS reaches a cell with value x, all possible next cells are already stored in:

product_to_cells[x]

This avoids recomputing factor pairs during the search.

We also use two visited structures:

visited[r][c]
expanded[x]

visited[r][c] means the cell has already been added to the BFS queue.

expanded[x] means we have already processed all cells in product_to_cells[x]. This matters because many different cells can contain the same value.

Python Solution

from collections import deque


def solve():
    M = int(input())
    N = int(input())

    grid = [[0] * (N + 1)]
    for _ in range(M):
        grid.append([0] + list(map(int, input().split())))

    max_product = M * N

    product_to_cells = [[] for _ in range(max_product + 1)]
    for r in range(1, M + 1):
        for c in range(1, N + 1):
            product_to_cells[r * c].append((r, c))

    visited = [[False] * (N + 1) for _ in range(M + 1)]
    expanded = [False] * (max_product + 1)

    q = deque([(1, 1)])
    visited[1][1] = True

    while q:
        r, c = q.popleft()

        if r == M and c == N:
            print("yes")
            return

        value = grid[r][c]
        if value < 1 or value > max_product:
            continue

        if expanded[value]:
            continue

        expanded[value] = True

        for nr, nc in product_to_cells[value]:
            if not visited[nr][nc]:
                visited[nr][nc] = True
                q.append((nr, nc))

    print("no")


solve()

C++ Solution

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M, N;
    cin >> M >> N;

    vector<vector<int>> grid(M + 1, vector<int>(N + 1));
    for (int r = 1; r <= M; r++) {
        for (int c = 1; c <= N; c++) {
            cin >> grid[r][c];
        }
    }

    int maxProduct = M * N;

    vector<vector<pair<int, int>>> productToCells(maxProduct + 1);
    for (int r = 1; r <= M; r++) {
        for (int c = 1; c <= N; c++) {
            productToCells[r * c].push_back({r, c});
        }
    }

    vector<vector<bool>> visited(M + 1, vector<bool>(N + 1, false));
    vector<bool> expanded(maxProduct + 1, false);

    queue<pair<int, int>> q;
    q.push({1, 1});
    visited[1][1] = true;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        if (r == M && c == N) {
            cout << "yes\n";
            return 0;
        }

        int value = grid[r][c];
        if (value < 1 || value > maxProduct) {
            continue;
        }

        if (expanded[value]) {
            continue;
        }

        expanded[value] = true;

        for (auto [nr, nc] : productToCells[value]) {
            if (!visited[nr][nc]) {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }

    cout << "no\n";
    return 0;
}

Complexity Analysis

Building the product index processes every cell once, so it takes:

O(MN)

During BFS, each cell is added to the queue at most once. Each product list is expanded at most once, and all product lists together contain exactly MN cell coordinates.

The total time complexity is:

O(MN)

The memory complexity is:

O(MN)

Common Mistakes

1. Treating the problem as four-direction grid movement.
2. Forgetting that coordinates are 1-indexed.
3. Recomputing factor pairs every time a cell is visited.
4. Not using expanded[value], which causes repeated scans of the same destination list.
5. Forgetting to skip values larger than M * N.
6. Looking for a shortest path when the problem only asks whether the exit is reachable.

Review Questions

1. Why is Escape Room an implicit graph problem?
2. What does product_to_cells[x] store?
3. Why do we need both visited[r][c] and expanded[x]?
4. Why can a value larger than M * N lead nowhere?
5. Would DFS also work for this problem? Why?