2
$\begingroup$

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!

Improve this question
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Apr 3, 2022 at 13:37
  • $\begingroup$ 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? $\endgroup$
    – stackoverload
    Apr 3, 2022 at 13:43
  • $\begingroup$ You can use an MST algorithm, though probably there are better options. $\endgroup$
    – Yuval Filmus
    Apr 3, 2022 at 13:44
  • $\begingroup$ @stackoverload Could you please mention the source URL of this problem? $\endgroup$
    – John L.
    Apr 3, 2022 at 13:44
  • 1
    $\begingroup$ @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 $\endgroup$
    – stackoverload
    Apr 3, 2022 at 13:48

1 Answer 1

Reset to default
1
$\begingroup$

You can use a graph traversal algorithm such as BFS/DFS to detect the connected components, and to construct a graph in which the vertices are connected components and the edges are walls adjacent to two connected components. A spanning tree in this graph corresponds to the walls that need to be removed.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.