CCC 2020 - 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.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;