Minimum Path without Bomb

Question

A 2-D matrix of size N x M is given. Data in each cell represents the time to cross the cell. Some blocks are containing negative values denoting a bomb. We need to find minimum time of reaching to [n-1 , m-1] from [0 , 0] without passing through any bomb.

• Do i need to do BFS here or Dijkstra here? If I do BFS, how does it determine shortest time / minimum time?
• If I do Dijkstra, how do I get a path from [0, 0] cell to [n-1, m-1].

Example Matrix:

                        {0, 4, -1, -1, -1, -1, -1, 8, -1},
                        {4, 0, 8, -1, -1, -1, -1, 11, -1},
                        {-1, 8, 0, 7, -1, 4, -1, -1, 2},
                        {-1, -1, 7, 0, 9, 14, -1, -1, -1},
                        {-1, -1, -1, 9, 0, 10, -1, -1, 1},
                        {-1, -1, 4, -1, 10, 0, 2, -1, -1},
                        {-1, -1, -1, 14, -1, 2, 0, 1, 6},
                        {8, 11, -1, -1, -1, -1, 1, 0, 7},
                        {-1, -1, 2, -1, -1, -1, 6, 7, 0}

Answer 1

If the 2D matrix is made as a graph, then the cost of traversal of each edge is same. In that case, Djikstra's is equivalent to a BFS. Since each cell has a different cost of crossing, Djikstra isn't equivalent to BFS here. BFS will determine minimum number of cells needed to cross, but not the minimum time. So the requirement is of Djiksta's. This answers your first query.

I'm assuming you know how to implement Djikstra's. The issue which you are facing is how to implement it on this question. For that, you need to represent a 2D matrix as a graph. The main question which arises is how to capture the relationship of node values in a graph. This may arise because you are used to thinking of weights on edges, but not on vertices. However, you can simply reduce problem to Djikstra's by making it a directed graph, where the cost of edge of from [i][k] to [j][k] as the value of [j][k], and the cost of edge in the backwards direction as value of [i][k]. To incorporate the concept of a bomb, simply don't generate vertices for those cells. After this, applying Djikstra's should be straightforward.

Answer 2

Create a graph from the 2D grid (each location is a node, edges to the locations above, below, to the right and the left. Bomb locations just don't go in), but after you've done the initial creation, use step 2:

Let's say node (x,y) has value 8, and it is accessible from four nodes (in the grid: one above, to the right, the left and below). You transform the node into 4 nodes - one adjacent to each neighbor and these four nodes are connected between themselves (clique) with edges of value 8.

Once this is done on all the graph, run Dijkstra...