4

Minimize cost to move from [0, 0] to [N-1, M-1] using given orthogonal and diago...

 1 year ago
source link: https://www.geeksforgeeks.org/minimize-cost-to-move-from-0-0-to-n-1-m-1-using-given-orthogonal-and-diagonal-moves//
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Minimize cost to move from [0, 0] to [N-1, M-1] using given orthogonal and diagonal moves

  • Difficulty Level : Hard
  • Last Updated : 17 Apr, 2023

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: 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++ 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;
}
Output

Time Complexity: O(N * M)  
Auxiliary Space: O(N * M)

Related Articles:

Like Article
Save Article

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK