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\dots 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.

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;