Minimum Cost to cross Grid

The idea is to convert this problem as a graph problem. Each cell of the grid can be considered as a graph vertex and their costs can be considered as the weight of the vertices. We will add unweighted edges between all the pairs of adjacent cells. Using the above observations, the problem can be simplified to finding the shortest path between the Top-Left cell and Bottom-Right cell. This can be done efficiently with the help of the Dijkstra algorithm. Note that we do not need to explicitly build a graph, as we will be using the fact that for a particular cell, all edges from it exist with its adjacent cells only.

Steps: 

1. Let cost be a N*M 2-D matrix where cost[i][j] stores the minimum total cost to reach cell (i,j) starting from cell (0,0). Initialize all values of the matrix as INT_MAX.
2. Let heap be a min-heap that will be used for implementing the Dijkstra algorithm. The heap stores the row and column of each cell, and it also stores the cost to reach that cell which is also used as the comparison operator to build the heap.
3. Let deltaX be an array of 4 integers that stores the difference of the X-coordinates of the cell with its neighbours. Add the 4 integers  -1, 1, 0 and 0 to the array deltaX.
4. Let deltaY be an array of 4 integers that stores the difference of the Y-coordinates of the cell with its neighbours. Add the 4 integers 0, 0, 1 and -1 to the array deltaY.
5. Add the cell (0,0) having cost MAT[0][0] to the heap, and set cost[0][0] as MAT[0][0].
6. While the heap is non-empty, then
   • Pop an element from the heap. Let the extracted cell be (x,y).
   • Iterate from i = 0 to 3
     • Let currX be x + deltaX and currY be y + deltaY, where (currX,currY) denotes the neighbour cell that is currently being considered.
     • If the cell (currX,currY) lies inside the grid, then
       • Let newCost denote the  cost to reach the cell (currX,currY). Set newCost as cost[x][y] + MAT[currX][currY].
       • If newCost is smaller than cost[currX][currY], then
         • Set cost[currX][currY] as currCost
         • Insert the cell (currX,currY) to the heap.;
7. Return the value cost[N-1][M-1] as the cell (N-1,M-1) denotes the bottom-right cell.

O(N * M * log(N * M), where ‘N’ and ‘M’ denotes the number of rows and columns in the grid, respectively.

Since we are using Dijkstra's algorithm for finding minimum cost and the time complexity of this algorithm is O(|V| * log(|V|) + |E| *  log(|V|)) where |V| is the number of vertices and |E| is the number of edges in the graph. In our construction, there are (N * M) vertices and at max (4 * N * M) edges. Hence, the overall Time Complexity is O(N * M * log(N * M).

O(N * M), where ‘N’ and ‘M’ denotes the number of rows and columns in the grid, respectively.

Since we are using cost matrix of N * M dimension to store the costs and we are also using a min-heap which stores at max N * M elements. Hence, the overall space complexity is O(N * M).