Problem link: MAZE Problem - CodeChef
I need help in understanding where my solution Solution fails.
Logic:
We represent the corners of each cell as nodes and the walls as edges. We make a connection between two corners of a cell by an edge if its wall is painted. The boundary of the maze is already connected and we represent it using single node say 0. The rest of the corners are represented by other numbers.
So a 4 X 4 grid will look like
0-0-0-0-0
| | | | |
0-1-2-3-0
| | | | |
0-4-5-6-0
| | | | |
0-7-8-9-0
| | | | |
0-0-0-0-0
Some queries and their corresponding representation:
1 2 1 3 → 0 - 2 (we make a vertical edge between node 0 and node 2)
2 1 3 1 → 0 - 4 (we make a horizontal edge between node 0 and node 4)
Approach:
- If the already painted walls represented as edges form a cycle then the answer is 0. We use a disjoint set union data structure to check if the edges form a cycle
- If on adding a new edge we get a cycle then the answer is 1.
- Else the answer is 2.