Given a two-dimensional matrix of size N x M. The data in each cell represents the time required to cross the cell. Some blocks contain negative values for the bomb. We need to find the minimum time to reach [n-1, m-1] from [0, 0] without passing any bomb.
- Do I need to do BFS or Dijkstra here? If I am doing BFS, how to determine the minimum time / minimum time?
- If I do Dijkstra, how can I get the path from cell [0, 0] to [n-1, m-1].
Matrix example:
{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}