# Make maze connected removing minimal number of obstacles

Input consists of two numbers $$n$$ (number of rows) and $$m$$ (number of columns) with the maze consisting of $$2\cdot n + 1$$ rows, where each row consists of $$2\cdot m + 1$$ symbols: ‘+’, ‘-‘, ‘|’, ‘.’

First and last rows stand for horizontal borders of maze.

First and last columns stand for vertical borders of maze.

Cells with even coordinates are ‘.’ symbol

Cells with odd coordinate are ‘+’ symbol

Other cells can be ‘.’ , ‘|’ or ‘-‘

We should change minimal number of ‘|’ or ‘-‘ in order to have connected inner space of maze (connected means that every ‘.’ is connected to others).

Consider input n = 2, m = 3 with maze $$\begin{matrix} +& -& +& -& +& -& +\ |& .& |& .& .& .& |\ +& -& +& -& +& -& +\ |& .& |& .& .& .& |\ +& -& +& -& +& -& + \end{matrix}$$

The answer is one of the possible solutions, for example $$\begin{matrix} +& -& +& -& +& -& +\ |& .& .& .& .& .& |\ +& .& +& -& +& -& +\ |& .& .& .& .& .& |\ +& -& +& -& +& -& + \end{matrix}$$

My idea is to make groups of connected inner spaces (in this picture we will have 4 groups with two groups consisting of 1 dot and two others consisting of 3 dots) and then to reduce amount of them while it remains only one.

Will this work or maybe there is a better solution to this problem?