Minimize cost to reach a cell in Matrix using horizontal, vertical and diagonal moves

Given two points P1(x1y1) and P2(x2y2) of a matrix, the task is to find the minimum cost to reach P2 from P1 when:

  • A horizontal or vertical movement in any direction cost 1 unit
  • A diagonal movement in any direction costs 0 unit.

Examples:

Input: P1 = {7, 4}, P2 = {4, 4}
Output: 1
Explanation: The movements are given below given below:

Movements are (7, 4) -> (6, 5) -> (5, 5) -> (4, 4).
As there is only 1 vertical movement so cost will be 1.

Input: P1 = {1, 2}, P2 = {2, 2}
Output: 1

Approach: The movements should be such that there is minimum horizontal or vertical movement. This can be decided from the following observation:

If the horizontal distance is h = (y2 – y1) and the vertical distance between the points is v = (x2 – x1):
If |h – v| is even, only diagonal movements are enough.
Because horizontal or vertical positions can be maintained with two opposite diagonal movements as shown in the image below:

maintaining vertical position

And when horizontal and vertical distances become the same, then can directly move to P2 using diagonal movements.
But in case this value is odd then one vertical or horizontal movement is required to make it even.

For this follow the below steps:

  • Find the vertical distance from P1 to P2. Let say it is vert.
  • Find the horizontal distance from P1 to P2. Let say it is hori.
  • There will always be a way from source to destination by moving diagonally if |hori – vert| is even.
  • But if |hori – vert| is odd then 1 step either horizontal or vertical is required after that only diagonal movement will be sufficient.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

int minCostToExit(int x1, int y1, int x2, int y2)

{

    

    

    int vert = abs(x2 - x1);

    

    

    int hori = abs(y1 - y2);

    

    if (abs(hori - vert) % 2 == 0)

        return 0;

    else

        return 1;

}

int main()

{

    int x1 = 7;

    int y1 = 4;

    int x2 = 4, y2 = 4;

    int cost = minCostToExit(x1, y1, x2, y2);

    cout << cost;

    return 0;

}

Java

class GFG {

  

  static int minCostToExit(int x1, int y1,

                           int x2, int y2)

  {

    

    

    int vert = Math.abs(x2 - x1);

    

    

    int hori = Math.abs(y1 - y2);

    

    if (Math.abs(hori - vert) % 2 == 0)

      return 0;

    else

      return 1;

  }

  

  public static void main(String args[]) {

    int x1 = 7;

    int y1 = 4;

    int x2 = 4, y2 = 4;

    int cost = minCostToExit(x1, y1, x2, y2);

    System.out.println(cost);

  }

}

Python3

import math as Math

def minCostToExit (x1, y1, x2, y2):

    

    

    vert = Math.fabs(x2 - x1);

    

    

    hori = Math.fabs(y1 - y2);

    

    if (Math.fabs(hori - vert) % 2 == 0):

        return 0;

    else:

        return 1;

x1 = 7

y1 = 4

x2 = 4

y2 = 4;

cost = minCostToExit(x1, y1, x2, y2);

print(cost);

C#

using System;

class GFG {

  

  static int minCostToExit(int x1, int y1, int x2, int y2)

  {

    

    

    int vert = Math.Abs(x2 - x1);

    

    

    int hori = Math.Abs(y1 - y2);

    

    if (Math.Abs(hori - vert) % 2 == 0)

      return 0;

    else

      return 1;

  }

  

  public static void Main()

  {

    int x1 = 7;

    int y1 = 4;

    int x2 = 4, y2 = 4;

    int cost = minCostToExit(x1, y1, x2, y2);

    Console.Write(cost);

  }

}

Javascript

<script>

    

    

    const minCostToExit = (x1, y1, x2, y2) => {

    

        

        

        let vert = Math.abs(x2 - x1);

        

        

        let hori = Math.abs(y1 - y2);

        

        if (Math.abs(hori - vert) % 2 == 0)

            return 0;

        else

            return 1;

    }

    

    let x1 = 7;

    let y1 = 4;

    let x2 = 4, y2 = 4;

    let cost = minCostToExit(x1, y1, x2, y2);

    document.write(cost);

</script>

Time Complexity: O(1)
Auxiliary Space: O(1)

Leave a Comment