Minimum Manhattan distance covered by visiting every coordinates from a source to a final vertex

0 0 9 minutes read

Given an array arr[] of co-ordinate points and a source and final co-ordinate point, the task is to find the minimum manhattan distance covered from the source to the final vertex such that every point of the array is visited exactly once.

Manhattan Distance = $\left | x2 - x1 \right | + \left | y2 - y1 \right |$

Examples:

Input: source = (0, 0), final = (100, 100)
arr[] = {(70, 40), (30, 10), (10, 5), (90, 70), (50, 20)}
Output: 200
Input: source = (0, 0), final = (5, 5)
arr[] = {(1, 1)}
Output: 10

Approach: The idea is to use permutation and combination to generate every possible permutation movements to the co-ordinates and then compute the total manhattan distance covered by moving from the first co-ordinate of the array to the final co-ordinate and If the final distance covered is less than the minimum distance covered till now. Then update the minimum distance covered.
Below is the implementation of the above approach:

C++

// C++ implementation to find the 
// minimum manhattan distance
// covered by visiting N co-ordinates
 
#include <bits/stdc++.h>
using namespace std;
 
// Class of co-ordinates
class pairs {
public:
    int x;
    int y;
};
 
// Function to calculate the 
// manhattan distance between 
// pair of points
int calculate_distance(pairs a, 
                       pairs b)
{
    return abs(a.x - b.x) + 
           abs(a.y - b.y);
}
 
// Function to find the minimum 
// distance covered for visiting 
// every co-ordinate point
int findMinDistanceUtil(vector<int> nodes, 
           int noOfcustomer, int** matrix)
{
    int mindistance = INT_MAX;
     
    // Loop to compute the distance
    // for every possible permutation
    do {
        int distance = 0;
        int prev = 1;
         
        // Computing every total manhattan
        // distance covered for the every 
        // co-ordinate points
        for (int i = 0; i < noOfcustomer; i++) {
            distance = distance + 
                       matrix[prev][nodes[i]];
            prev = nodes[i];
        }
         
        // Adding the final distance
        distance = distance + matrix[prev][0];
         
        // if distance is less than 
        // minimum value then update it
        if (distance < mindistance)
            mindistance = distance;
    }while (
        next_permutation(
            nodes.begin(), nodes.end()
        ));
    return mindistance;
}
 
// Function to initialize the input
// and find the minimum distance 
// by visiting every coordinate
void findMinDistance()
{
    int noOfcustomer = 1;
    vector<pairs> coordinate;
    vector<int> nodes;
    // filling the coordinates into vector
    pairs office, home, customer;
    office.x = 0;
    office.y = 0;
    coordinate.push_back(office);
    home.x = 5;
    home.y = 5;
    coordinate.push_back(home);
    customer.x = 1;
    customer.y = 1;
    coordinate.push_back(customer);
     
    // make a 2d matrix which stores
    // distance between two point
    int** matrix = new int*[noOfcustomer + 2];
     
    // Loop to compute the distance between
    // every pair of points in the co-ordinate
    for (int i = 0; i < noOfcustomer + 2; i++) {
        matrix[i] = new int[noOfcustomer + 2];
         
        for (int j = 0; j < noOfcustomer + 2; j++) {
            matrix[i][j] = calculate_distance(
                    coordinate[i], coordinate[j]);
        }
         
        // Condition to not move the 
        // index of the source or 
        // the final vertex
        if (i != 0 && i != 1)
            nodes.push_back(i);
    }
    cout << findMinDistanceUtil(
        nodes, noOfcustomer, matrix);
}
 
// Driver Code
int main()
{
    // Function Call
    findMinDistance();
    return 0;
}

Java

// Java implementation to find the minimum manhattan
// distance covered by visiting N co-ordinates
 
import java.io.*;
import java.util.*;
 
// Class of co-ordinates
class Pair {
    int x;
    int y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
 
class GFG {
 
    // Function to calculate the manhattan distance between
    // pair of points
    static int calculateDistance(Pair a, Pair b)
    {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }
 
    // Function to find the minimum distance covered for
    // visiting every co-ordinate point
    static int findMinDistanceUtil(List<Integer> nodes,
                                   int noOfcustomer,
                                   int[][] matrix)
    {
        int minDistance = Integer.MAX_VALUE;
        int[] perm = new int[nodes.size()];
        for (int i = 0; i < nodes.size(); i++) {
            perm[i] = nodes.get(i);
        }
 
        // Loop to compute the distance for every possible
        // permutation
        do {
            int distance = 0;
            int prev = 1;
 
            // Computing every total manhattan distance
            // covered for the every co-ordinate points
            for (int i = 0; i < noOfcustomer; i++) {
                distance = distance + matrix[prev][perm[i]];
                prev = perm[i];
            }
 
            // Adding the final distance
            distance = distance + matrix[prev][0];
 
            // if distance is less than minimum value then
            // update it
            if (distance < minDistance) {
                minDistance = distance;
            }
        } while (nextPermutation(perm));
 
        return minDistance;
    }
 
    static boolean nextPermutation(int[] perm)
    {
        int i = perm.length - 2;
        while (i >= 0 && perm[i] >= perm[i + 1]) {
            i--;
        }
        if (i == -1) {
            return false;
        }
        int j = perm.length - 1;
        while (perm[j] <= perm[i]) {
            j--;
        }
        swap(perm, i, j);
        reverse(perm, i + 1);
        return true;
    }
 
    static void reverse(int[] perm, int start)
    {
        int i = start, j = perm.length - 1;
        while (i < j) {
            swap(perm, i, j);
            i++;
            j--;
        }
    }
 
    static void swap(int[] perm, int i, int j)
    {
        int temp = perm[i];
        perm[i] = perm[j];
        perm[j] = temp;
    }
 
    // Function to initialize the input and find the minimum
    // distance by visiting every coordinate
    static void findMinDistance()
    {
        int noOfCustomers = 1;
        List<Pair> coordinates = new ArrayList<>();
        List<Integer> nodes = new ArrayList<>();
        // filling the coordinates into vector
        Pair office = new Pair(0, 0);
        Pair home = new Pair(5, 5);
        Pair customer = new Pair(1, 1);
        coordinates.add(office);
        coordinates.add(home);
        coordinates.add(customer);
 
        // make a 2d matrix which stores distance between
        // two point
        int[][] matrix
            = new int[noOfCustomers + 2][noOfCustomers + 2];
 
        // Loop to compute the distance between every pair
        // of points in the co-ordinate
        for (int i = 0; i < noOfCustomers + 2; i++) {
            for (int j = 0; j < noOfCustomers + 2; j++) {
                matrix[i][j] = calculateDistance(
                    coordinates.get(i), coordinates.get(j));
            }
 
            // Condition to not move the index of the source
            // or the final vertex
            if (i != 0 && i != 1) {
                nodes.add(i);
            }
        }
 
        System.out.println(findMinDistanceUtil(
            nodes, noOfCustomers, matrix));
    }
 
    public static void main(String[] args)
    {
        // Function Call
        findMinDistance();
    }
}
 
// This code is contributed by karthik.

C#

// C# implementation to find the minimum manhattan distance
// covered by visiting N co-ordinates
 
using System;
using System.Collections.Generic;
 
public class Pair {
    public int x;
    public int y;
    public Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
 
public class GFG {
 
    static int CalculateDistance(Pair a, Pair b)
    {
        return Math.Abs(a.x - b.x) + Math.Abs(a.y - b.y);
    }
 
    static int FindMinDistanceUtil(List<int> nodes,
                                   int noOfCustomers,
                                   int[, ] matrix)
    {
        int minDistance = int.MaxValue;
        int[] perm = new int[nodes.Count];
        for (int i = 0; i < nodes.Count; i++) {
            perm[i] = nodes[i];
        }
 
        do {
            int distance = 0;
            int prev = 1;
            for (int i = 0; i < noOfCustomers; i++) {
                distance = distance + matrix[prev, perm[i]];
                prev = perm[i];
            }
            distance = distance + matrix[prev, 0];
            if (distance < minDistance) {
                minDistance = distance;
            }
        } while (NextPermutation(perm));
 
        return minDistance;
    }
 
    static bool NextPermutation(int[] perm)
    {
        int i = perm.Length - 2;
        while (i >= 0 && perm[i] >= perm[i + 1]) {
            i--;
        }
        if (i == -1) {
            return false;
        }
        int j = perm.Length - 1;
        while (perm[j] <= perm[i]) {
            j--;
        }
        Swap(perm, i, j);
        Reverse(perm, i + 1);
        return true;
    }
 
    static void Reverse(int[] perm, int start)
    {
        int i = start, j = perm.Length - 1;
        while (i < j) {
            Swap(perm, i, j);
            i++;
            j--;
        }
    }
 
    static void Swap(int[] perm, int i, int j)
    {
        int temp = perm[i];
        perm[i] = perm[j];
        perm[j] = temp;
    }
 
    static void FindMinDistance()
    {
        int noOfCustomers = 1;
        List<Pair> coordinates = new List<Pair>();
        List<int> nodes = new List<int>();
        Pair office = new Pair(0, 0);
        Pair home = new Pair(5, 5);
        Pair customer = new Pair(1, 1);
        coordinates.Add(office);
        coordinates.Add(home);
        coordinates.Add(customer);
        int[, ] matrix
            = new int[noOfCustomers + 2, noOfCustomers + 2];
        for (int i = 0; i < noOfCustomers + 2; i++) {
            for (int j = 0; j < noOfCustomers + 2; j++) {
                matrix[i, j] = CalculateDistance(
                    coordinates[i], coordinates[j]);
            }
 
            // Condition to not move the index of the source
            // or the final vertex
            if (i != 0 && i != 1) {
                nodes.Add(i);
            }
        }
 
        Console.WriteLine(FindMinDistanceUtil(
            nodes, noOfCustomers, matrix));
    }
 
    static public void Main()
    {
 
        // Code
        // Function Call
        FindMinDistance();
    }
}
 
// This code is contributed by lokesh.

Javascript

// Class of co-ordinates
class Pair {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}
 
// Function to calculate the 
// manhattan distance between pair of points
function calculateDistance(a, b) {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
 
// Function to find the minimum distance 
// covered for visiting every co-ordinate point
function findMinDistanceUtil(nodes, noOfcustomer, matrix) {
  let minDistance = Number.MAX_SAFE_INTEGER;
  let perm = new Array(nodes.length);
  for (let i = 0; i < nodes.length; i++) {
    perm[i] = nodes[i];
  }
 
  // Loop to compute the distance for every possible permutation
  do {
    let distance = 0;
    let prev = 1;
 
    // Computing every total manhattan distance 
    // covered for the every co-ordinate points
    for (let i = 0; i < noOfcustomer; i++) {
      distance = distance + matrix[prev][perm[i]];
      prev = perm[i];
    }
 
    // Adding the final distance
    distance = distance + matrix[prev][0];
 
    // if distance is less than minimum value then update it
    if (distance < minDistance) {
      minDistance = distance;
    }
  } while (nextPermutation(perm));
 
  return minDistance;
}
 
function nextPermutation(perm) {
  let i = perm.length - 2;
  while (i >= 0 && perm[i] >= perm[i + 1]) {
    i--;
  }
  if (i == -1) {
    return false;
  }
  let j = perm.length - 1;
  while (perm[j] <= perm[i]) {
    j--;
  }
  swap(perm, i, j);
  reverse(perm, i + 1);
  return true;
}
 
function reverse(perm, start) {
  let i = start,
    j = perm.length - 1;
  while (i < j) {
    swap(perm, i, j);
    i++;
    j--;
  }
}
 
function swap(perm, i, j) {
  let temp = perm[i];
  perm[i] = perm[j];
  perm[j] = temp;
}
 
// Function to initialize the input and 
// find the minimum distance by visiting every coordinate
function findMinDistance() {
  let noOfCustomers = 1;
  let coordinates = [];
  let nodes = [];
   
  // filling the coordinates into array
  let office = new Pair(0, 0);
  let home = new Pair(5, 5);
  let customer = new Pair(1, 1);
  coordinates.push(office);
  coordinates.push(home);
  coordinates.push(customer);
 
  // make a 2d matrix which stores distance between two point
  let matrix = new Array(noOfCustomers + 2);
  for (let i = 0; i < noOfCustomers + 2; i++) {
    matrix[i] = new Array(noOfCustomers + 2);
    for (let j = 0; j < noOfCustomers + 2; j++) {
      matrix[i][j] = calculateDistance(coordinates[i], coordinates[j]);
    }
 
    // Condition to not move the index of the source or the final vertex
    if (i != 0 && i != 1) {
      nodes.push(i);
    }
  }
 
  console.log(findMinDistanceUtil(nodes, noOfCustomers, matrix));
}
 
// Function Call
findMinDistance();

Python

import itertools
 
# Class of coordinates
class Pair:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
# Function to calculate the manhattan distance between pair of points
def calculate_distance(a, b):
    return abs(a.x - b.x) + abs(a.y - b.y)
 
# Function to find the minimum distance covered for visiting every coordinate point
def find_min_distance_util(nodes, no_of_customer, matrix):
    mindistance = float('inf')
 
    # Loop to compute the distance for every possible permutation
    for perm in itertools.permutations(nodes):
        distance = 0
        prev = 1
         
        # Computing every total manhattan distance covered for the every coordinate points
        for i in range(no_of_customer):
            distance += matrix[prev][perm[i]]
            prev = perm[i]
         
        # Adding the final distance
        distance += matrix[prev][0]
         
        # if distance is less than minimum value then update it
        if distance < mindistance:
            mindistance = distance
    return mindistance
 
# Function to initialize the input and find the minimum distance by visiting every coordinate
def find_min_distance():
    no_of_customer = 1
    coordinate = []
    nodes = []
     
    # filling the coordinates into list
    office = Pair(0, 0)
    coordinate.append(office)
    home = Pair(5, 5)
    coordinate.append(home)
    customer = Pair(1, 1)
    coordinate.append(customer)
     
    # make a 2d matrix which stores distance between two points
    matrix = [[0 for i in range(no_of_customer + 2)] for j in range(no_of_customer + 2)]
     
    # Loop to compute the distance between every pair of points in the coordinate
    for i in range(no_of_customer + 2):
        for j in range(no_of_customer + 2):
            matrix[i][j] = calculate_distance(coordinate[i], coordinate[j])
             
        # Condition to not move the index of the source or the final vertex
        if i != 0 and i != 1:
            nodes.append(i)
     
    print(find_min_distance_util(nodes, no_of_customer, matrix))
 
# Driver code
find_min_distance()

Output:

Performance Analysis:

Time Complexity: O(N! * N)
Auxiliary Space: O(N²)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!