Maze Connectivity 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.
 A: 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:


*

*start with a graph $G_0$ representing your initial state.

*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\}$.


*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).
A: 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.
