Recently I've stumbled upon a strange graph problem. Here is a brief description.
Given $n\times m$ matrix with $2n + 1$ rows such that each row contains $2m + 1$ characters "+", "-", "|", "."
- First, last row, and first, last column are the borders of the maze.
- Even coordinates, e.g. (0, 0), (0, 2), are filled with "+", which you can't step on.
- Odd coordinates are filled with ".", which is used normally for the traversal.
- The rest of the coordinates share "|", "-", "." characters. "|" defines a horizontal wall, whereas "-" defines vertical.
The problem asks to delete a minimal number of walls, i.e. "|" and "-", in order to make the whole maze connected.
The example is given below
Input
2 3
+-+-+-+
|.|...|
+-+-+-+
|.|...|
+-+-+-+
Output
2 3
+-+-+-+
|.....|
+.+-+-+
|.|...|
+-+-+-+
As you can see two walls are deleted, the vertical wall having the coordinate $(1, 2) $ and the horizontal wall with the coordinates $(2, 1)$.
This problem seems like a perfect application of Disjoint Set Union, but I am not convinced that this is any right approach to this problem. Any help is much appreciated!