Maze Connectivity

Question

Given a grid maze which is an n × m rectangle maze where each cell is either empty, or is a wall. One can go from one cell to another only if both cells are empty and have a common side.

Initially we have a grid maze with all empty cells(denoted by .) forming a connected area. That is, we can go from any empty cell to any other one. Now we want to turn exactly k empty cells into walls so that all the remaining cells still formed a connected area. How to tackle this problem

EXAMPLE :

Let us consider a grid of 3*4 and let k=2,meaning we need to built two walls

INITIAL GRID :

N . . N

. . N .

N . . .

SOLUTION FOR THIS EXAMPLE WILL BE

N . x N

x . N .

N . . .

Here x denotes the wall,as their can be many solutions , i need any one of them.

N denotes Non empty cells here.

Answer 1

Consider the 'dual' way of representing your problem: consider the cells as vertices of a graph, with edges between vertices exactly when they share an edge in the grid. Then 'occupying' a cell is just removing its vertex (and of course all adjacent edges) from the graph.

From this point of view, the cells that are unsafe for placement — that is, the ones that will split your region into two disjoint regions — are known as the articulation points or cut vertices of the graph. There's a classical algorithm, due to Robert Tarjan, for finding all of the articulation points by building a DFS (Depth-First Search) tree from the graph and then scanning it appropriately. This then leads to an algorithm for your problem:

1. start with a graph $G_0$ representing your initial state.
2. for $i$ from $0$ to $k-1$:
   • Find the set $C$ of all the cut vertices of the graph $G_i$ using the Tarjan algorithm or something similar (unfortunately, I don't know of any 'dynamic' algorithms that update the cut-vertex set as the graph changes, so you may need to run the full algorithm each time here; fortunately this shouldn't be too bad for any reasonably-sized graph.)
   • Choose a vertex $v_i$ at random from $v(G_i)-C$, the set of all non-cut vertices of the graph.
   • Remove that vertex from the graph, giving the new graph $G_{i+1} = G_i-\{v_i\}$.
3. Now, your final graph $G_k$ will still be connected (by construction), and the set of removed vertices $\{v_i\}$ will be the new 'wall' cells.

One cautionary note: it's actually possible for this process to 'get stuck' and not be able to remove $k$ vertices because it made poor choices early, even if it was possible from the original position to successfully remove a set of $k$. As long as $k$ is relatively small, this shouldn't happen in practice, but if you expect this to be a concern then you may need an even smarter algorithm (but note that the problem is likely to become NP-complete in a hurry).

Answer 2

You can add as many as you like. Here is the proof. For any recatngle suppose you want to add $k$ walls to a space of the size $a\cdot b$ with $k\leq a\cdot b$. Then take any connected space of size $a\cdot b-k$ and color all of the remaining cells.