Minimize cost to move from [0, 0] to [N-1, M-1] using given orthogonal and diagonal moves
Given a matrix A[][] of size N * M columns each element consists of either 0 representing free space and 1 representing wall. In one operation you can move from the current cell to Up, Down, Left or Right with 0 cost and move diagonally with cost 1. The task is to find the minimum cost to travel from top-left to bottom-right.
Examples:
Input: A[][] = {{0, 0, 1, 0}, {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 0}};
Output: 1
Explanation: One possible route is {0, 0} -> {0, 1} -> {1, 1} -> {2, 2} -> {3, 2} -> {3, 3}Input: A[][] = {{0, 0, 1, 0, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 1}, {1, 0, 1, 0, 1}, {0, 0, 1, 0, 0}}
Output: 2
Approach 1: To solve the problem follow the below idea:
The concept of 0-1 BFS can be used to solve the above problem. We can visualize the grid as a graph with every cell of grid as node and travelling diagonally costs 1 and travelling horizontal or vertical costs 0.
Below are the steps for the above approach:
- Create a deque to implement the BFS.
- Create a matrix dist[N][M] and initialize it with INT_MAX and set the initial position dist[0][0] to 0.
- Push the source to deque.
- Perform the following till the deque becomes empty:
- Store the top element in a temporary variable (say V) and remove it from the deque.
- Iterate through all the possible free neighbours (orthogonally and diagonally).
- Store the possible free neighbour in the queue.
- Update the minimum cost to reach the neighbour in the dist[][] matrix based on its movement from the current cell.
- The value stored in dist[N-1][M-1] is the minimum possible cost. So return this as the required answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // king path int dx[] = { 1, -1, 0, 0, 1, -1, 1, -1 }, dy[] = { 0, 0, 1, -1, 1, 1, -1, -1 }; // Function to check if given coordinates // are inside the grid or not bool ok( int X, int Y, int N, int M) { return X >= 0 and Y >= 0 and X < N and Y < M; } // Function to find minimum cost to // traverse from (0, 0) to (N-1, M-1) int minCost(vector<vector< int > >& A, int N, int M) { // Deque for 0-1 bfs deque<pair< int , int > > dq; // Distance array vector<vector< int > > dist(N, vector< int >(M, INT_MAX)); // Dource distance initialized // with zero dist[0][0] = 0; // Pushing back source in deque dq.push_back({ 0, 0 }); // Running while loop until nothing // is left in deque while (!dq.empty()) { // Front element of deque pair< int , int > v = dq.front(); // Erasing front element of deque dq.pop_front(); for ( int i = 0; i < 8; i++) { // New coordinates int newX = v.first + dx[i], newY = v.second + dy[i]; if (ok(newX, newY, N, M) and A[newX][newY] == 0) { // Travelling digonally if (i > 3 and dist[newX][newY] > dist[v.first][v.second] + 1) { dist[newX][newY] = dist[v.first][v.second] + 1; dq.push_back({ newX, newY }); } else if (i <= 3 and dist[newX][newY] > dist[v.first] [v.second]) { dist[newX][newY] = dist[v.first][v.second]; dq.push_front({ newX, newY }); } } } } // returning the final answer return dist[N - 1][M - 1]; } // Driver Code int32_t main() { // Input 1 int N = 4, M = 4; vector<vector< int > > A = { { 0, 0, 1, 0 }, { 0, 0, 1, 0 }, { 0, 1, 0, 0 }, { 0, 1, 0, 0 } }; // Function Call cout << minCost(A, N, M) << endl; // Input 2 int N1 = 5, M1 = 5; vector<vector< int > > A1 = { { 0, 0, 1, 0, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 1 }, { 0, 0, 1, 0, 0 } }; // Function Call cout << minCost(A1, N1, M1) << endl; return 0; } |
Java
import java.util.*; public class Main { // king path static int [] dx = { 1 , - 1 , 0 , 0 , 1 , - 1 , 1 , - 1 }; static int [] dy = { 0 , 0 , 1 , - 1 , 1 , 1 , - 1 , - 1 }; // Function to check if given coordinates // are inside the grid or not static boolean ok( int X, int Y, int N, int M) { return X >= 0 && Y >= 0 && X < N && Y < M; } // Function to find minimum cost to // traverse from (0, 0) to (N-1, M-1) static int minCost( int [][] A, int N, int M) { // Deque for 0-1 bfs Deque<Pair> dq = new ArrayDeque<>(); // Distance array int [][] dist = new int [N][M]; for ( int i = 0 ; i < N; i++) { Arrays.fill(dist[i], Integer.MAX_VALUE); } // Source distance initialized // with zero dist[ 0 ][ 0 ] = 0 ; // Pushing back source in deque dq.addLast( new Pair( 0 , 0 )); // Running while loop until nothing // is left in deque while (!dq.isEmpty()) { // Front element of deque Pair v = dq.pollFirst(); for ( int i = 0 ; i < 8 ; i++) { // New coordinates int newX = v.first + dx[i]; int newY = v.second + dy[i]; if (ok(newX, newY, N, M) && A[newX][newY] == 0 ) { // Travelling diagonally if (i > 3 && dist[newX][newY] > dist[v.first][v.second] + 1 ) { dist[newX][newY] = dist[v.first][v.second] + 1 ; dq.addLast( new Pair(newX, newY)); } else if (i <= 3 && dist[newX][newY] > dist[v.first] [v.second]) { dist[newX][newY] = dist[v.first][v.second]; dq.addFirst( new Pair(newX, newY)); } } } } // returning the final answer return dist[N - 1 ][M - 1 ]; } // Pair class to store coordinates static class Pair { int first, second; public Pair( int first, int second) { this .first = first; this .second = second; } } // Driver Code public static void main(String[] args) { // Input 1 int N = 4 , M = 4 ; int [][] A = { { 0 , 0 , 1 , 0 }, { 0 , 0 , 1 , 0 }, { 0 , 1 , 0 , 0 }, { 0 , 1 , 0 , 0 } }; // Function Call System.out.println(minCost(A, N, M)); // Input 2 int N1 = 5 , M1 = 5 ; int [][] A1 = { { 0 , 0 , 1 , 0 , 0 }, { 1 , 0 , 1 , 0 , 1 }, { 1 , 1 , 0 , 1 , 1 }, { 1 , 0 , 1 , 0 , 1 }, { 0 , 0 , 1 , 0 , 0 } }; // Function Call System.out.println(minCost(A1, N1, M1)); } } // This code is contributed by abhinav_m22 |
Python
# King path dx = [ 1 , - 1 , 0 , 0 , 1 , - 1 , 1 , - 1 ] dy = [ 0 , 0 , 1 , - 1 , 1 , 1 , - 1 , - 1 ] # Function to check if given coordinates # are inside the grid or not def ok(X, Y, N, M): return X > = 0 and Y > = 0 and X < N and Y < M # Function to find minimum cost to # traverse from (0, 0) to (N-1, M-1) def minCost(A, N, M): # Deque for 0-1 bfs dq = [] # Distance array dist = [[ float ( 'inf' )] * M for _ in range (N)] # Source distance initialized with zero dist[ 0 ][ 0 ] = 0 # Pushing back source in deque dq.append(( 0 , 0 )) # Running while loop until nothing is left in deque while dq: # Front element of deque v = dq.pop( 0 ) for i in range ( 8 ): # New coordinates newX = v[ 0 ] + dx[i] newY = v[ 1 ] + dy[i] if ok(newX, newY, N, M) and A[newX][newY] = = 0 : # Traveling diagonally if i > 3 and dist[newX][newY] > dist[v[ 0 ]][v[ 1 ]] + 1 : dist[newX][newY] = dist[v[ 0 ]][v[ 1 ]] + 1 dq.append((newX, newY)) elif i < = 3 and dist[newX][newY] > dist[v[ 0 ]][v[ 1 ]]: dist[newX][newY] = dist[v[ 0 ]][v[ 1 ]] dq.insert( 0 , (newX, newY)) # Returning the final answer return dist[N - 1 ][M - 1 ] # Driver code if __name__ = = "__main__" : # Input 1 N = 4 M = 4 A = [[ 0 , 0 , 1 , 0 ], [ 0 , 0 , 1 , 0 ], [ 0 , 1 , 0 , 0 ], [ 0 , 1 , 0 , 0 ]] # Function Call print (minCost(A, N, M)) # Input 2 N1 = 5 M1 = 5 A1 = [[ 0 , 0 , 1 , 0 , 0 ], [ 1 , 0 , 1 , 0 , 1 ], [ 1 , 1 , 0 , 1 , 1 ], [ 1 , 0 , 1 , 0 , 1 ], [ 0 , 0 , 1 , 0 , 0 ]] # Function Call print (minCost(A1, N1, M1)) # This code was contributed by codearcade |
C#
using System; using System.Collections.Generic; class MainClass { // King path static int [] dx = { 1, -1, 0, 0, 1, -1, 1, -1 }; static int [] dy = { 0, 0, 1, -1, 1, 1, -1, -1 }; // Function to check if given coordinates // are inside the grid or not static bool Ok( int X, int Y, int N, int M) { return X >= 0 && Y >= 0 && X < N && Y < M; } // Function to find minimum cost to // traverse from (0, 0) to (N-1, M-1) static int MinCost( int [][] A, int N, int M) { // Queue for 0-1 BFS Queue<Pair> dq = new Queue<Pair>(); // Distance array int [,] dist = new int [N, M]; for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { dist[i, j] = int .MaxValue; } } // Source distance initialized // with zero dist[0, 0] = 0; // Pushing back source in queue dq.Enqueue( new Pair(0, 0)); // Running while loop until nothing // is left in queue while (dq.Count > 0) { // Front element of queue Pair v = dq.Dequeue(); for ( int i = 0; i < 8; i++) { // New coordinates int newX = v.first + dx[i]; int newY = v.second + dy[i]; if (Ok(newX, newY, N, M) && A[newX][newY] == 0) { // Travelling diagonally if (i > 3 && dist[newX, newY] > dist[v.first, v.second] + 1) { dist[newX, newY] = dist[v.first, v.second] + 1; dq.Enqueue( new Pair(newX, newY)); } else if (i <= 3 && dist[newX, newY] > dist[v.first, v.second]) { dist[newX, newY] = dist[v.first, v.second]; dq.Enqueue( new Pair(newX, newY)); } } } } // returning the final answer return dist[N - 1, M - 1]; } // Pair class to store coordinates class Pair { public int first, second; public Pair( int first, int second) { this .first = first; this .second = second; } } // Driver Code public static void Main( string [] args) { // Input 1 int N = 4, M = 4; int [][] A = { new int [] { 0, 0, 1, 0 }, new int [] { 0, 0, 1, 0 }, new int [] { 0, 1, 0, 0 }, new int [] { 0, 1, 0, 0 } }; // Function Call Console.WriteLine(MinCost(A, N, M)); // Input 2 int N1 = 5, M1 = 5; int [][] A1 = { new int [] { 0, 0, 1, 0, 0 }, new int [] { 1, 0, 1, 0, 1 }, new int [] { 1, 1, 0, 1, 1 }, new int [] { 1, 0, 1, 0, 1 }, new int [] { 0, 0, 1, 0, 0 } }; // Function Call Console.WriteLine(MinCost(A1, N1, M1)); } } |
Javascript
// King path const dx = [1, -1, 0, 0, 1, -1, 1, -1]; const dy = [0, 0, 1, -1, 1, 1, -1, -1]; // Function to check if given coordinates are inside the grid or not function ok(X, Y, N, M) { return X >= 0 && Y >= 0 && X < N && Y < M; } // Function to find minimum cost to traverse from (0, 0) to (N-1, M-1) function minCost(A, N, M) { // Queue for BFS const queue = []; // Distance array const dist = new Array(N).fill().map(() => new Array(M).fill(Number.POSITIVE_INFINITY)); // Source distance initialized with zero dist[0][0] = 0; // Enqueue source coordinates queue.push([0, 0]); // Running while loop until the queue is empty while (queue.length > 0) { // Front element of the queue const v = queue.shift(); for (let i = 0; i < 8; i++) { // New coordinates const newX = v[0] + dx[i]; const newY = v[1] + dy[i]; if (ok(newX, newY, N, M) && A[newX][newY] === 0) { // Traveling diagonally if (i > 3 && dist[newX][newY] > dist[v[0]][v[1]] + 1) { dist[newX][newY] = dist[v[0]][v[1]] + 1; queue.push([newX, newY]); } else if (i <= 3 && dist[newX][newY] > dist[v[0]][v[1]]) { dist[newX][newY] = dist[v[0]][v[1]]; queue.unshift([newX, newY]); } } } } // Returning the final answer return dist[N - 1][M - 1]; } // Driver code ( function () { // Input 1 const N = 4; const M = 4; const A = [ [0, 0, 1, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 1, 0, 0] ]; // Function Call console.log(minCost(A, N, M)); // Input 2 const N1 = 5; const M1 = 5; const A1 = [ [0, 0, 1, 0, 0], [1, 0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 0, 1, 0, 1], [0, 0, 1, 0, 0] ]; // Function Call console.log(minCost(A1, N1, M1)); })(); // This code is contributed by Dwaipayan Bandyopadhyay |
1 2
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Approach 2:
Below are the steps for the approach :
- Use a priority queue (min heap) to prioritize cells with lower distances, resulting in a more efficient approach.
- We can maintain a 2D distance array to store the minimum distance from the top-left cell to each cell in the matrix.
- Start from the top-left cell and initialize its distance as 0, push it into the priority queue.
- While the priority queue is not empty, pop the cell with the minimum distance.
- Explore all 8 neighboring cells (up, down, left, right, and diagonals) and calculate the cost to reach each neighboring cell from the current cell.
- If the calculated cost is less than the current distance of the neighboring cell, update the distance and push the neighboring cell into the priority queue.
- Repeat steps 4-6 until the bottom-right cell is reached or all possible cells are explored.
- Return the distance of the bottom-right cell as the minimum cost to travel from top-left to bottom-right.
Here is the code for above approach :
C++
#include <bits/stdc++.h> using namespace std; // King path int dx[] = { 1, -1, 0, 0, 1, -1, 1, -1 }, dy[] = { 0, 0, 1, -1, 1, 1, -1, -1 }; // Function to check if given coordinates // are inside the grid or not bool ok( int X, int Y, int N, int M) { return X >= 0 and Y >= 0 and X < N and Y < M; } // Function to find minimum cost to // traverse from (0, 0) to (N-1, M-1) int minCost(vector<vector< int > >& A, int N, int M) { // Distance array vector<vector< int > > dist(N, vector< int >(M, INT_MAX)); // Source distance initialized // with zero dist[0][0] = 0; // Priority queue for Dijkstra's Algorithm priority_queue<pair< int , pair< int , int > >, vector<pair< int , pair< int , int > > >, greater<pair< int , pair< int , int > > > > pq; // Pushing source in priority queue pq.push({ 0, { 0, 0 } }); // Running Dijkstra's Algorithm while (!pq.empty()) { // Top element of priority queue pair< int , pair< int , int > > v = pq.top(); // Erasing top element of priority queue pq.pop(); int curDist = v.first; int curX = v.second.first; int curY = v.second.second; // If the current distance is greater than // the distance in distance array, skip it if (curDist > dist[curX][curY]) continue ; for ( int i = 0; i < 8; i++) { // New coordinates int newX = curX + dx[i], newY = curY + dy[i]; if (ok(newX, newY, N, M) && A[newX][newY] == 0) { int cost = 0; // If diagonal move, set cost to 1 if (i > 3) cost = 1; int newDist = curDist + cost; // If the new distance is smaller than // the distance in distance array, update it if (newDist < dist[newX][newY]) { dist[newX][newY] = newDist; pq.push({ newDist, { newX, newY } }); } } } } // Returning the final answer return dist[N - 1][M - 1]; } // Driver Code int main() { // Input 1 int N = 4, M = 4; vector<vector< int > > A = { { 0, 0, 1, 0 }, { 0, 0, 1, 0 }, { 0, 1, 0, 0 }, { 0, 1, 0, 0 } }; // Function Call cout << minCost(A, N, M) << endl; // Input 2 int N1 = 5, M1 = 5; vector<vector< int > > A1 = { { 0, 0, 1, 0, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 1 }, { 0, 0, 1, 0, 0 } }; // Function Call cout << minCost(A1, N1, M1) << endl; return 0; } |
Java
import java.util.*; public class GFG { // King path static int [] dx = { 1 , - 1 , 0 , 0 , 1 , - 1 , 1 , - 1 }; static int [] dy = { 0 , 0 , 1 , - 1 , 1 , 1 , - 1 , - 1 }; // Function to check if given coordinates // are inside the grid or not static boolean ok( int X, int Y, int N, int M) { return X >= 0 && Y >= 0 && X < N && Y < M; } // Function to find minimum cost to // traverse from (0, 0) to (N-1, M-1) static int minCost(List<List<Integer> > A, int N, int M) { // Distance array int [][] dist = new int [N][M]; for ( int i = 0 ; i < N; i++) { Arrays.fill(dist[i], Integer.MAX_VALUE); } // Source distance initialized // with zero dist[ 0 ][ 0 ] = 0 ; // Priority queue for Dijkstra's Algorithm PriorityQueue<Pair> pq = new PriorityQueue<>( Comparator.comparingInt(p -> p.dist)); // Pushing source in priority queue pq.add( new Pair( 0 , 0 , 0 )); // Running Dijkstra's Algorithm while (!pq.isEmpty()) { // Top element of priority queue Pair v = pq.poll(); int curDist = v.dist; int curX = v.x; int curY = v.y; // If the current distance is greater than // the distance in distance array, skip it if (curDist > dist[curX][curY]) continue ; for ( int i = 0 ; i < 8 ; i++) { // New coordinates int newX = curX + dx[i], newY = curY + dy[i]; if (ok(newX, newY, N, M) && A.get(newX).get(newY) == 0 ) { int cost = 0 ; // If diagonal move, set cost to 1 if (i > 3 ) cost = 1 ; int newDist = curDist + cost; // If the new distance is smaller than // the distance in distance array, // update it if (newDist < dist[newX][newY]) { dist[newX][newY] = newDist; pq.add( new Pair(newDist, newX, newY)); } } } } // Returning the final answer return dist[N - 1 ][M - 1 ]; } // Pair class for storing coordinates and distance static class Pair { int dist, x, y; public Pair( int dist, int x, int y) { this .dist = dist; this .x = x; this .y = y; } } // Driver Code public static void main(String[] args) { // Input 1 int N = 4 , M = 4 ; List<List<Integer> > A = Arrays.asList(Arrays.asList( 0 , 0 , 1 , 0 ), Arrays.asList( 0 , 0 , 1 , 0 ), Arrays.asList( 0 , 1 , 0 , 0 ), Arrays.asList( 0 , 1 , 0 , 0 )); // Function Call System.out.println(minCost(A, N, M)); // Input 2 int N1 = 5 , M1 = 5 ; List<List<Integer> > A1 = Arrays.asList(Arrays.asList( 0 , 0 , 1 , 0 , 0 ), Arrays.asList( 1 , 0 , 1 , 0 , 1 ), Arrays.asList( 1 , 1 , 0 , 1 , 1 ), Arrays.asList( 1 , 0 , 1 , 0 , 1 ), Arrays.asList( 0 , 0 , 1 , 0 , 0 )); // Function Call System.out.println(minCost(A1, N1, M1)); } } |
Python
import heapq # King path dx = [ 1 , - 1 , 0 , 0 , 1 , - 1 , 1 , - 1 ] dy = [ 0 , 0 , 1 , - 1 , 1 , 1 , - 1 , - 1 ] # Function to check if given coordinates # are inside the grid or not def ok(X, Y, N, M): return 0 < = X < N and 0 < = Y < M # Function to find minimum cost to # traverse from (0, 0) to (N-1, M-1) def minCost(A, N, M): # Distance array dist = [[ float ( 'inf' ) for _ in range (M)] for _ in range (N)] # Source distance initialized # with zero dist[ 0 ][ 0 ] = 0 # Priority queue for Dijkstra's Algorithm pq = [( 0 , ( 0 , 0 ))] # Running Dijkstra's Algorithm while pq: # Top element of priority queue curDist, (curX, curY) = heapq.heappop(pq) # If the current distance is greater than # the distance in the distance array, skip it if curDist > dist[curX][curY]: continue for i in range ( 8 ): # New coordinates newX, newY = curX + dx[i], curY + dy[i] if ok(newX, newY, N, M) and A[newX][newY] = = 0 : cost = 0 # If diagonal move, set cost to 1 if i > 3 : cost = 1 newDist = curDist + cost # If the new distance is smaller than # the distance in the distance array, update it if newDist < dist[newX][newY]: dist[newX][newY] = newDist heapq.heappush(pq, (newDist, (newX, newY))) # Returning the final answer return dist[N - 1 ][M - 1 ] # Driver Code if __name__ = = "__main__" : # Input 1 N = 4 M = 4 A = [ [ 0 , 0 , 1 , 0 ], [ 0 , 0 , 1 , 0 ], [ 0 , 1 , 0 , 0 ], [ 0 , 1 , 0 , 0 ] ] # Function Call print (minCost(A, N, M)) # Input 2 N1 = 5 M1 = 5 A1 = [ [ 0 , 0 , 1 , 0 , 0 ], [ 1 , 0 , 1 , 0 , 1 ], [ 1 , 1 , 0 , 1 , 1 ], [ 1 , 0 , 1 , 0 , 1 ], [ 0 , 0 , 1 , 0 , 0 ] ] # Function Call print (minCost(A1, N1, M1)) |
C#
using System; using System.Collections.Generic; public class GFG { // King path static int [] dx = { 1, -1, 0, 0, 1, -1, 1, -1 }; static int [] dy = { 0, 0, 1, -1, 1, 1, -1, -1 }; // Function to check if given coordinates // are inside the grid or not static bool Ok( int X, int Y, int N, int M) { return X >= 0 && Y >= 0 && X < N && Y < M; } // Function to find minimum cost to // traverse from (0, 0) to (N-1, M-1) static int MinCost(List<List< int >> A, int N, int M) { // Distance array int [,] dist = new int [N, M]; for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { dist[i, j] = int .MaxValue; } } // Source distance initialized // with zero dist[0, 0] = 0; // Custom PriorityQueue for Dijkstra's Algorithm var pq = new PriorityQueue<Pair>((p1, p2) => p1.dist.CompareTo(p2.dist)); // Pushing source in priority queue pq.Enqueue( new Pair(0, 0, 0)); // Running Dijkstra's Algorithm while (pq.Count > 0) { // Top element of priority queue Pair v = pq.Dequeue(); int curDist = v.dist; int curX = v.x; int curY = v.y; // If the current distance is greater than // the distance in distance array, skip it if (curDist > dist[curX, curY]) continue ; for ( int i = 0; i < 8; i++) { // New coordinates int newX = curX + dx[i]; int newY = curY + dy[i]; if (Ok(newX, newY, N, M) && A[newX][newY] == 0) { int cost = 0; // If diagonal move, set cost to 1 if (i > 3) cost = 1; int newDist = curDist + cost; // If the new distance is smaller than // the distance in distance array, // update it if (newDist < dist[newX, newY]) { dist[newX, newY] = newDist; pq.Enqueue( new Pair(newDist, newX, newY)); } } } } // Returning the final answer return dist[N - 1, M - 1]; } // Pair class for storing coordinates and distance public class Pair { public int dist, x, y; public Pair( int dist, int x, int y) { this .dist = dist; this .x = x; this .y = y; } } // Custom PriorityQueue implementation public class PriorityQueue<T> { private List<T> list; private Comparison<T> comparison; public PriorityQueue(Comparison<T> comparison) { this .list = new List<T>(); this .comparison = comparison; } public void Enqueue(T item) { list.Add(item); int i = list.Count - 1; while (i > 0) { int j = (i - 1) / 2; if (comparison(list[i], list[j]) >= 0) break ; T tmp = list[i]; list[i] = list[j]; list[j] = tmp; i = j; } } public T Dequeue() { int last = list.Count - 1; T frontItem = list[0]; list[0] = list[last]; list.RemoveAt(last); last--; int parent = 0; while ( true ) { int left = parent * 2 + 1; if (left > last) break ; int right = left + 1; if (right <= last && comparison(list[right], list[left]) < 0) left = right; if (comparison(list[left], list[parent]) >= 0) break ; T tmp = list[left]; list[left] = list[parent]; list[parent] = tmp; parent = left; } return frontItem; } public int Count { get { return list.Count; } } } // Driver Code public static void Main( string [] args) { // Input 1 int N = 4, M = 4; List<List< int >> A = new List<List< int >> { new List< int > {0, 0, 1, 0}, new List< int > {0, 0, 1, 0}, new List< int > {0, 1, 0, 0}, new List< int > {0, 1, 0, 0} }; // Function Call Console.WriteLine(MinCost(A, N, M)); // Input 2 int N1 = 5, M1 = 5; List<List< int >> A1 = new List<List< int >> { new List< int > {0, 0, 1, 0, 0}, new List< int > {1, 0, 1, 0, 1}, new List< int > {1, 1, 0, 1, 1}, new List< int > {1, 0, 1, 0, 1}, new List< int > {0, 0, 1, 0, 0} }; // Function Call Console.WriteLine(MinCost(A1, N1, M1)); } } |
Javascript
// Pair class for storing coordinates and distance class Pair { constructor(dist, x, y) { this .dist = dist; this .x = x; this .y = y; } } // Function to find minimum cost to // traverse from (0, 0) to (N-1, M-1) function minCost(A, N, M) { const dx = [1, -1, 0, 0, 1, -1, 1, -1]; const dy = [0, 0, 1, -1, 1, 1, -1, -1]; // Function to check if given coordinates // are inside the grid or not function ok(X, Y) { return X >= 0 && Y >= 0 && X < N && Y < M; } // Distance array const dist = new Array(N).fill().map(() => new Array(M).fill(Number.MAX_VALUE)); dist[0][0] = 0; // Priority queue for Dijkstra's Algorithm const pq = new PriorityQueue((a, b) => a.dist - b.dist); // Pushing source in priority queue pq.enqueue( new Pair(0, 0, 0)); // Running Dijkstra's Algorithm while (!pq.isEmpty()) { // taking out top element const v = pq.dequeue(); const curDist = v.dist; const curX = v.x; const curY = v.y; // If the current distance is greater than // the distance in distance array, skip it if (curDist > dist[curX][curY]) continue ; for (let i = 0; i < 8; i++) { // new co-ordinates const newX = curX + dx[i]; const newY = curY + dy[i]; if (ok(newX, newY) && A[newX][newY] === 0) { // If diagonal move, set cost to 1 const cost = i > 3 ? 1 : 0; const newDist = curDist + cost; // If the new distance is smaller than // the distance in distance array, update it if (newDist < dist[newX][newY]) { dist[newX][newY] = newDist; pq.enqueue( new Pair(newDist, newX, newY)); } } } } // returning final answer return dist[N - 1][M - 1]; } // Creating Priority Queue class class PriorityQueue { constructor(comparator) { this .data = []; this .comparator = comparator || ((a, b) => a - b); } // enqueue method enqueue(element) { this .data.push(element); this .bubbleUp( this .data.length - 1); } // dequeue method dequeue() { if ( this .isEmpty()) { return null ; } const root = this .data[0]; const last = this .data.pop(); if ( this .data.length > 0) { this .data[0] = last; this .sinkDown(0); } return root; } // method to check queue is empty or not isEmpty() { return this .data.length === 0; } // bubble up method bubbleUp(index) { while (index > 0) { const parentIndex = Math.floor((index - 1) / 2); if ( this .comparator( this .data[index], this .data[parentIndex]) < 0) { [ this .data[index], this .data[parentIndex]] = [ this .data[parentIndex], this .data[index]]; index = parentIndex; } else { break ; } } } // sink dowm method sinkDown(index) { while ( true ) { const leftChildIndex = 2 * index + 1; const rightChildIndex = 2 * index + 2; let smallestChildIndex = index; if (leftChildIndex < this .data.length && this .comparator( this .data[leftChildIndex], this .data[smallestChildIndex]) < 0) { smallestChildIndex = leftChildIndex; } if (rightChildIndex < this .data.length && this .comparator( this .data[rightChildIndex], this .data[smallestChildIndex]) < 0) { smallestChildIndex = rightChildIndex; } if (smallestChildIndex !== index) { [ this .data[index], this .data[smallestChildIndex]] = [ this .data[smallestChildIndex], this .data[index]]; index = smallestChildIndex; } else { break ; } } } } // Test case - 1 const N1 = 4; const M1 = 4; const A1 = [ [0, 0, 1, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 1, 0, 0] ]; // calling minCost function console.log(minCost(A1, N1, M1)); // Test case - 2 const N2 = 5; const M2 = 5; const A2 = [ [0, 0, 1, 0, 0], [1, 0, 1, 0, 1], [1, 1, 0, 1, 1], [1, 0, 1, 0, 1], [0, 0, 1, 0, 0] ]; console.log(minCost(A2, N2, M2)); |
Output :
1
2
Complexity Analysis :
The time complexity of the given code is O(N*Mlog(N*M)), where N is the number of rows in the grid and M is the number of columns in the grid. This is because the code uses Dijkstra’s algorithm, which has a time complexity of O(Vlog(V)) for a graph with V vertices. In this case, the grid has N*M vertices, so the time complexity is O(N*Mlog(N*M)).
The space complexity of the given code is O(N*M), as we are using a 2D vector of size N*M to store the distance array. Additionally, the priority queue used in the Dijkstra’s algorithm may have at most N*M elements at any point in time, so it does not add to the space complexity. Overall, the space complexity is O(N*M).
Related Articles: