CCC 20 J5 / S2 - Escape Room

Author: Benjamin Qi

Table of Contents

Edit on Github

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

So we essentially have a directed graph with vertices where there exists a directed edge from x to grid[r][c] whenever . We want to test whether there exists a path from to in this graph.

Thus, we can simply start DFSing from vertex 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];
5void 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.