# Make maze connected by removing internal walls

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!

• You can use BFS/DFS to find the connected components and the walls separating them. If there are $C$ connected components, you need to remove $C-1$ walls, which form a spanning tree in the graph whose vertices are the components and whose edges correspond to walls. Apr 3, 2022 at 13:37
• Beautiful. You can post the solution and I can accept it. One small question though, how to detect the walls that need to be deleted? Apr 3, 2022 at 13:43
• You can use an MST algorithm, though probably there are better options. Apr 3, 2022 at 13:44
• @stackoverload Could you please mention the source URL of this problem? Apr 3, 2022 at 13:44
• @JohnL. no problem at all. Here is a link contest.yandex.ru/contest/12341/enter. You need to register and check the last problem. I was translating this problem as well Apr 3, 2022 at 13:48