Find shortest distance of every cell from landmine in a Maze

Given a Maze in the form of a rectangular matrix, filled with either O, X or M, where O represents an open cell, X represents a blocked cell and M represents landmines in the maze, we need to find shortest distance of every open cell in the maze from its nearest mine.

 
We’re only allowed to travel in either of the four directions and diagonal moves are not allowed. We can assume cells with the mine have distance 0. Also, blocked cells and unreachable cells have distance -1.

 
For example,


Input: 6 x 5 matrix filled with O(Open cell), X(Blocked Cell), and M(LandMine)

O   M   O   O   X
O   X   X   O   M
O   O   O   O   O
O   X   X   X   O
O   O   M   O   O
O   X   X   M   O

Output:

1   0   1   2  -1
2  -1  -1   1   0
3   4   3   2   1
3  -1  -1  -1   2
2   1   0   1   2
3  -1  -1   0   1

 
The idea is to do a BFS procedure to solve this problem. We start by creating an empty queue and enqueuing all cells with the mines. Then we loop through the queue and for each of four adjacent cells of the front cell, we enqueue it (with updated distance) if represents an open space and its distance from the mine is not yet calculated. We repeat the procedure till queue is not empty.

 
C++ implementation –

 

Download   Run Code

Output:

1   0   1   2  -1
2  -1  -1   1   0
3   4   3   2   1
3  -1  -1  -1   2
2   1   0   1   2
3  -1  -1   0   1

 

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

Notify of
avatar
wpDiscuz