Circular Maze
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: brute force, dfs and similar, graphs, implementation

You are given a circular maze such as the ones shown in the figures.

- Circular walls are described by a radius $$$r$$$, the distance from the center, and two angles $$$\theta_1, \theta_2$$$ describing the beginning and the end of the wall in the clockwise direction. Notice that swapping the two angles changes the wall.
- Straight walls are described by an angle $$$\theta$$$, the direction of the wall, and two radii $$$r_1 < r_2$$$ describing the beginning and the end of the wall.

Angles are measured in degrees; the angle $$$0$$$ corresponds to the upward pointing direction; and angles increase clockwise (hence the east direction corresponds to the angle $$$90$$$).

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 20$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the number of walls.

Each of the following $$$n$$$ lines each contains a character (C for circular, and S for straight) and three integers:

- either $$$r, \theta_1, \theta_2$$$ ($$$1 \leq r \leq 20$$$ and $$$0 \leq \theta_1,\theta_2 < 360$$$ with $$$\theta_1 \neq \theta_2$$$) if the wall is circular,
- or $$$r_1$$$, $$$r_2$$$ and $$$\theta$$$ ($$$1 \leq r_1 < r_2 \leq 20$$$ and $$$0 \leq \theta < 360$$$) if the wall is straight.

It is guaranteed that circular walls do not overlap (but two circular walls may intersect at one or two points), and that straight walls do not overlap (but two straight walls may intersect at one point). However, circular and straight walls can intersect arbitrarily.

Output format:
For each test case, print YES if the maze can be solved and NO otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The two sample test cases correspond to the two mazes in the picture.

Example input:
2
5
C 1 180 90
C 5 250 230
C 10 150 140
C 20 185 180
S 1 20 180
6
C 1 180 90
C 5 250 230
C 10 150 140
C 20 185 180
S 1 20 180
S 5 10 0

Example output:
YES
NO

Editorial:
In this task, you are given circular mazes described by collections of walls, which can be either circular (constant radius) or straight (constant angle). The goal is to determine if a maze can be solved, that is, if there is a path from the center to the outside which does not cross any wall.
Reducing the problem to a grid maze
The first remark to be made is that this task can be reformulated into the much simpler problem of finding a path in a grid maze (with the left and right sides of the grid being connected by some portal). The image bellow illustrates the grid obtained from the first input sample, where each row corresponds to a radius (between $$$1$$$ and $$$20$$$) and each column corresponds to an angle (between $$$0$$$ and $$$360$$$). A possible path solving the maze is displayed in orange.

The first part of the solution consists of building the grid maze, and fill 2D arrays with the walls. Because walls do not overlap, it is sufficient to iterate over each wall (number of operations is in the order of $$$t \cdot 20 \cdot 360 \leq 10^6$$$). Observe that with overlapping walls, the naïve implementation might be too slow (worst case is $$$t \cdot n \cdot 360 \geq 10^8$$$), but one could compute cumulative sums of arrays containing the endpoints of walls.
Finally, we build the undirected graph where each cell is connected to the neighbouring cells such that there is no wall in between.
Solving the grid maze
Now that we have a grid maze, where each cell is connected to up to $$$4$$$ neighbours, we need to determine if there is a path between the inside and the outside of the maze. The only remaining detail is to describe how we deal with the inside (below radius $$$r=1$$$) and the outside of the maze (above radius $$$r=20$$$). Multiple approaches exist:
• Adding two "sentinel" rows of cells to the maze, one at the bottom (inside) and one at the top (outside). Because there are no walls in sentinel rows, it is enough to pick (arbitrarily) one cell from each row and check if there is a path between them.
• Adding two special cells, one for the inside and one for the outside, connected (when there is no wall) to cells from the bottom and the top row. It is now enough to check if there is a path between these two special cells.
Finally, checking if there is a path between two cells can be done with various algorithms computing the connected components of a graph.
• Depth-first search: the procedure builds the component of a starting cell by exploring (recursively) adjacent cells, making sure it does not explore the same cell twice.
• Breadth-first search: the procedure builds the component of a starting cell by exploring (iteratively) cells at distance $$$1$$$, then $$$2$$$, etc.
• Disjoint-Set Union data structure: starting from a collection of singleton sets (each containing one cell), the data structure can merge sets (containing two neighbouring cells). The resulting collection of sets corresponds to connected components.