# [Backrooms](https://open.kattis.com/problems/backrooms) Editorial

## Subtask 1/2: small coordinates (up to $500$)

Subtask 1 can be solved by case bashing. However, it's pretty tricky to get right, so it's probably better to just solve the case with small coordinates.

To solve the subtasks with small coordinates, we can simply create a finite set of copies of the grid. It suffices to take the rectangle $[0-K,500+K] \times [0-K,500+K]$ for some fixed $K$ proportional to $R$ and $C$ (say, $K=RC$), and find the connected components in this grid. The reason that $K$ is small is that since the grid is period, any path straying too far off $[0,500] \times [0,500]$ must itself be period, and there is thus a path that is closer to the area with the same reachability.

## Subtask 3: medium-large coordinates (up to $10^5$)
The easiest way to solve this subtask is to use the [$A^*$](https://en.wikipedia.org/wiki/A*_search_algorithm) algorithm, where the heuristic used is the manhattan distance to the goal. It might require a little fin-tuning.

There also exists another solution that is more informative to the rest of the problem. Let's visualize some examples to get some intuition for the problem. We will take the base pattern, tile it some times and then color the connected components.




As it turns out, these 3 types of grids are all possible ones. We will call them type 2, 1 and 0.

- Type 2 grids: there is a single infinitely large connected component.
- Type 1 grids: there is an infinite number of infitely large connected components. The connected components look like lines.
- Type 0 grids: every connected component is finite

This is still not a full characterization: type 2 and type 1 grids can also have an infinite number of finite connected components:



How does this help us actually solve the problem? First, check if any of the query endpoints is in a finite connected component. If so, a BFS will definitely be fast enough to check if the other query endpoint is in the same component. It can be proven that there a finite connected component cannot be larger than $O(RC)$.

If none are in a finite component, check if the grid is of type 2. If it is, the answer is definitely $\texttt{Yes}$. One way to do this is to create many copies of the grid, and check if the fraction of cells reachable from a single starting point is a constant fraction. The judge solution checks if the number of cells along the boundary that are reachable is greater than $2(R+C)$.

The only case left are type $1$ grids. In these, the distance between two points is clearly very similar to the manhattan distance if they are in the same connected component. Additionally, the number of points reachable within a bounded distance is linear in the distance. Thus, doing a BFS, where you break after visiting too many cells works.

So the only case where a BFS that breaks after visiting too many cells fails are type 2 grids. The reason that $A^*$ works so well is that in type 2 grids, $A^*$ quickly finds the goal in a linear number of steps.

## Subtask 4 and 5: $R, C \leq 5$

From the previous analysis, we already know how to solve type 2 and type 1 grids. Thus, the only case we don't know how to solve for big coordinates is type 1 grids (where none of the query endpoints are in a finite connected component).

To solve these, note that even if the shapes of the connected components are complicated, their complexity is bounded by the fact that our base pattern is so small.


Let's try to describe all reachable cells of a particular component with functions of the form

$$(a,b) + k(c,d)$$

where all numbers are integers. $k$ is a free parameter that is any integer. For example, I have drawn $(2,0)+k(4,4)$ as the white line and $(0,0)+k(1,1)$ as the gray line below. The red dot is the bottom left of $(0,0)$, right is $+x$ and up is $+y$.


We can show that $a,b,c,d$ don't need to be that large, since everything is periodic. It's possible to arrive at the following bounds

$$|a|,|b|,|c|,|d| \leq RC$$

Which means that we only have to brute over $50^4$ values, which is very managable. Doing this naively solves subtask $4$. By being careful when doing this brute and pre-answering all possible $(RC)^2$ questions at the same time, we solve subtask 5.

## Subtask 7

From here on, we need to be a bit more careful with ensuring everything runs fast enough; we can't just rely on $R$ and $C$ being tiny (and if you are sloppy but have the right ideas, you will get subtask 6). We define a tile to be a copy of the base pattern.

Let's add edges that connect the boundaries of the grid with each other as follows.


This graph captures how we can move around in the base pattern. A necessary condition for reachability is that both the start and end are in the same connected component. Another necessary condition is that we are able to switch tiles such that we reach the tile where the goal is placed in. Every time we cross an edge that wraps around, we will switch tile. These two together are sufficient for reachability.

Let's label the edges that wrap with vectors, denoting crossing it changes tiles.


For example, the vector $+(1,0)$ means that we switch to a tile one to the right. There are internal edges between cells too, all having the vector $(0,0)$. Let's call this graph the torus graph of our grid. Now, we want to check whether there is a way to walk around in this periodic, finite graph, such that the sum of vectors equals the desired tile displacement.

To make this tractable, let's restrict ourselves a little. For each connected component, let's designate some arbitrary cell to be the *root* of the component. Now, any walk of the form

$$\text{start} \rightarrow \text{...} \rightarrow \text{goal}$$

can be decomposed into

$$\text{start} \rightarrow \text{root} \rightarrow \text{...} \rightarrow \text{root} \rightarrow \text{...} \rightarrow \text{root} \rightarrow \text{goal}$$

(Where root could show up more or less times). Notice that the walks between adjacent roots (the $\text{...}$) must be a closed walk (cycle that is not necessarily simple). With this view, we only need to be able to consider all closed walks that start and end with $\text{root}$. This turns out to be possible: we can take an arbitrary spanning tree and root it at $\text{root}$. Then, every non-tree edge results in one cycle. We can walk along these vectors in any order an arbitrary amount of times. It turns out that by walking along these cycles in different orders fully captures all possible closed walks, at least when measured in the different tile offsets they generate (see [Cycle Basic](https://en.wikipedia.org/wiki/Cycle_basis)).

To quickly compute the sum of vectors for each cycle, do a DFS and compute the sum of vectors from the root to every node, only considering tree edges. We will call this the *displacement vector* for a given cell. Now, recall that every non-tree edge $(u,v)$ corresponds to the cycle:

$$\text{root} \rightarrow u \rightarrow v \rightarrow \text{root}$$

The net displacement of the cycle is $d_u+d_e+d_v$. Note that you also get $-d_u-d_e-d_v$, since the cycle can also be walked backwards, which negates all vectors.

The fact that walking along these cycles in different orders fully captures all walks means that we are able to arbitrarily take different tile displacement vectors and add them to our current tile coordinate. So we have now reduced the problem to "given a bunch of vectors, is there an integer linear combination with a specific value"?

Fully solving this subproblem is a little tricky. We can reuse ideas from before to make it easier. First, we check if the query endpoints are in the same connected component in the torus graph. If not, the answer is $\texttt{No}$. Otherwise:
- if all cycle vectors in the component are $(0,0)$, then the component is finite (type 0). We are in this branch if at least one the endpoints has this condition. Then, simply compare the displacement vectors with the tile of each. More concretely, let $T_s=(\frac{x_s}{C}, \frac{y_s}{R})$, and $d_s$ be its displacement vector. Define it similarly for the goal, $t$. Now, they are reachable iff

$$T_s-d_s=T_t-d_t$$

- if there does not exist some vector $d$, where all vectors are of the form $k \; d$ for an integer $k$, then at least one pair of vectors is linearly independent. In this case, the dimension of the spanned room is 2D, and which means that the component is of type 2. The answer to the query is then $\text{Yes}$. The the next case describes how to check this.

- Otherwise, we have a type $1$ component. Our subproblem is "given a bunch of vectors that lie on the same line, i.e. are all of the form $v=k \; d$" for some vector $d$, can a given vector be constructed by an integer linear combination of these"? The 1D version is "given a bunch of integers, is there an integer linear combination of these with value $x$"? Note that we do not require nonnegative coefficients: cycles can be walked in reverse. This is the reason that the problem doesn't just become subset-sum. This problem is well-known: the set of numbers constructible is exactly all multiples of the GCD of the numbers.
Extending this to 2D, take any vector: it must of the form $(k \; d_x, k \; d_y)$, which means we can find $k$ by taking the GCD of its $x$ and $y$ coordinate, allowing us to extract the direction vector $d$. Now that we have $d$, we can compute $k$ for every other vector. To answer our query, its $x$ and $y$ must obviously be divisible by the corresponding component of $d$. If they are, compute $k$ for the query vector, and check if it's constructible by using the 1D solution.

This fully solves the problem.