# CCC 20 J5 / S2 - Escape Room

Author: Benjamin Qi

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⋅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⋅c=x$.

So we essentially have a directed graph with vertices $1…10_{6}$ where there exists a directed edge from `x`

to `grid[r][c]`

whenever $r⋅c=x$. We want to test whether there exists a path from $1$ to $N⋅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`

.

1int M,N;2vi todo[1000005];3bool done[1000005];45void dfs(int x) {6 if (done[x]) return;7 if (x == N*M) {8 ps("yes");9 exit(0);10 }

## Give Us Feedback on CCC 20 J5 / S2 - Escape Room!

### Join the Discussion!

Feel free to voice your thoughts in the comments section.