CCC 20 J5 / S2 - Escape Room

Define grid[r][c] to be the integer in the $r$-th row of the $c$-th column of the input grid. Let done[x]=true if we can reach any cell $(r,c)$ such that $r\cdot c=x$ and false otherwise. If done[x] is true, then we also know that done[grid[r][c]] is true for all cells $(r,c)$ such that $r\cdot c=x$.

So we essentially have a directed graph with vertices $1\ldots 10^6$ where there exists a directed edge from x to grid[r][c] whenever $r\cdot c=x$. We want to test whether there exists a path from $1$ to $N\cdot M$ in this graph.

Thus, we can simply start DFSing from vertex $1$ and mark all the vertices that we visit in the boolean array done. If we set done[N*M]=true, then a path exists, and we can terminate after printing "yes." Note that in the code below, todo[x] denotes the adjacency list of x.

int M,N;
vi todo[1000005];
bool done[1000005];

void dfs(int x) {
    if (done[x]) return;
    if (x == N*M) {
        ps("yes");
        exit(0);
    }