Path to the nearest service station

Consider the given ‘GRID’ as an undirected graph where each cell represents a vertex, and if two free cells are adjacent, they are connected by an edge. Dijkstra’s algorithm is used for finding the shortest path between nodes in a weighted graph. As the given graph is unweighted, the path length is equal to the number of edges, so consider each edge’s weight to be ‘1’. Consider the cell with the ninja as the source node and break the algorithm when we reach a cell with a service station. There are ‘N x M’ vertices where each vertex is of the form ‘[r, c]’ (‘r’: row number, and ‘c’: column number). Below is an implementation of Dijkstra’s algorithm using priority queue(in this case: min-heap): 

First find the presence of ninja:

• Initialize two integers ‘SOURCEROW = -1’ and ‘SOURCECOL = -1’. Use them to store the location of the cell where the ninja is present.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
  • Run a loop where ‘j’ ranges from ‘0’ to ‘M - 1’:
    • If ‘GRID[i][j]’ is equal to ‘N’:
      • ‘SOURCEROW = i’ and ‘SOURCECOL = j’
      • Break the loop.
  • If ‘SOURCEROW ’ is not equal to ‘-1’:
    • Break the loop. We have found the cell with the ninja.

Now apply Dijkstra’s algorithm to find the minimum cost path to reach the target:

• Initialize 2-d array ‘path[n][m]’ with value ‘INT_MAX’. Use ‘PATH[i][j]’ to store the path length for cell ‘[i, j]’.
• Set ‘PATH[SOURCEROW ][SOURCERCOL] = 0’ (Length of the path to source vertex is zero).
• Create a min priority queue ‘MINPATH’ that stores ‘CELL’ objects and orders them by ‘CELL -> PATH’. A ‘CELL’ contains three values {‘PATH’, ‘ROW’, ‘COL’}.
• Insert {0, SOURCEROW , SOURCECOL}  in ‘MINPATH’. The value ‘PATH’ for the source vertex is zero.
• Initialize ‘DIR[4][2] = [(-1, 0), (0, 1), (1, 0), (0, -1)]. Add ‘DIR[i]’ to a cell to move to an adjacent cell in the direction: North, east, south or west.
• Run a loop until ‘MINPATH’ is not empty:
  • ‘CUR = MINPATH.pop()’. Get the vertex with the smallest known path length and remove it from ‘MINPATH’.
  • ‘ROW = CUR →ROW’ (Current row).
  • ‘COL = CUR →COL’ (Current column).
  • If ‘PATH[ROW][COL] < (CUR→PATH)’ then, ignore this instance of the cell as it doesn’t store the minimum path length:
    • Continue the loop.
  • If ‘GRID[ROW][COL]’ is equal to ‘S’, then this is the nearest service station:
    • Return ‘CUR→PATH’ as the answer.
  • Run a loop where ‘i’ ranges from 0 to 3:
    • ‘NEWROW = ROW + DIR[i][0]’. ‘NEWROW’ is the row no. of the adjacent cell.
    • ‘NEWCOL = COL + DIR[i][1]’. ‘NEWCOL’ is the column no. of the adjacent cell.
    • If ‘NEWROW >= N’ or ‘NEWROW < 0’ or ‘NEWCOL >= M’ or ‘NEWCOL < 0’ or  ‘GRID[NEWROW ][NEWCOL ]’ is equal to ‘X’ , then the adjacent cell is not a valid cell:
      • Continue the loop.
    • If ‘PATH[NEWROW ][NEWCOL ] > PATH[ROW][COL] + 1’, then:
      • ‘PATH[NEWROW ][NEWCOL ] = PATH[ROW][COL] + 1’
      • ‘MINPATH.push({path[NEWROW ][NEWCOL ], NEWROW , NEWCOL }).
• Return ‘-1’ as the answer as we cannot reach any cell with a service station.

Since the given grid can be considered as an unweighted graph, we can find the shortest path for each node in ‘O(E + V)’ = ‘O(M * N)’ time using a modified Breadth-first search algorithm. The shortest path length will be equivalent to the node’s level in the BFS traversal tree.

Proof of correctness: As we move level-wise in BFS, if a child node is not visited, it’s not reachable from any previous levels. Its shortest path will be equal to (parent node’s level + 1). Even if it’s reachable from any other node from the next levels, the corresponding path length will always be greater.

Following is a BFS implementation to solve this problem:

• Initialize two integers ‘SOURCEROW = -1’ and ‘SOURCECOL = -1’. Use them to store the location of the cell where the ninja is present.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
  • Run a loop where ‘j’ ranges from ‘0’ to ‘M - 1’:
    • If ‘GRID[i][j]’ is equal to ‘N’:
      • ‘SOURCEROW = i’ and ‘SOURCECOL = j’
      • Break the loop.
  • If ‘SOURCEROW ’ is not equal to ‘-1’:
    • Break the loop. We have found the cell with the ninja.
• Initialize 2-d array ‘PATH[N][M]’ with value ‘INT_MAX’. Use ‘PATH[i][j]’ to store the path length for cell ‘[i, j]’.
• Set ‘PATH[SOURCEROW ][SOURCECOL] = 0’ (Length of the path to source vertex is zero).
• Create a queue ‘BFSQ’ to perform BFS on the given graph.
• Push ‘[SOURCEROW, SOURCECOL]’ in ‘BFSQ’. This is the source vertex.
• Initialize ‘DIR[4][2] = [(-1, 0), (0, 1), (1, 0), (0, -1)]. Add ‘DIR[i]’ to a cell to move to an adjacent cell in the direction: North, east, south or west.
• Run a loop until ‘BFSQ’ is not empty:
  • ‘[ROW, COL] = BFSQ.pop()’
  • Run a loop where ‘i’ ranges from 0 to 3:
    • ‘NEWROW= ROW+ DIR[i][0]’. ‘NEWROW’ is row no. of the adjacent cell.
    • ‘NEWCOL= COL+ DIR[i][1]’. ‘NEWCOL’ is column no. of the adjacent cell.
    • If ‘NEWROW >= N’ or ‘NEWROW < 0’ or ‘NEWCOL >= M’ or ‘NEWCOL < 0’ or  ‘GRID[NEWROW][NEWCOL]’ is equal to ‘X’ , then the adjacent cell is not a valid cell:
      • Continue the loop.
    • If ‘PATH[NEWROW ][NEWCOL ] > PATH[ROW][COL] + 1’, then:
      • ‘PATH[NEWROW ][NEWCOL ] = PATH[ROW][COL] + 1’
      • If ‘GRID[NEWROW ][NEWCOL ]’ is equal to ‘S’, then this is the nearest service station:
        • Return ‘PATH[NEWROW ][NEWCOL ]’ as the answer.
      • ‘BFSQ.push([NEWROW , NEWCOL ])’
• Return ‘-1’ as the answer as we cannot reach any cell with a service station.