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 =
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-ordinatesclass pairs {public: int x; int y;};// Function to calculate the // manhattan distance between // pair of pointsint 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 pointint 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 coordinatevoid 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 Codeint main(){ // Function Call findMinDistance(); return 0;} |
Java
// Java implementation to find the minimum manhattan// distance covered by visiting N co-ordinatesimport java.io.*;import java.util.*;// Class of co-ordinatesclass 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-ordinatesusing 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-ordinatesclass Pair { constructor(x, y) { this.x = x; this.y = y; }}// Function to calculate the // manhattan distance between pair of pointsfunction 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 pointfunction 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 coordinatefunction 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 CallfindMinDistance(); |
Python
import itertools# Class of coordinatesclass Pair: def __init__(self, x, y): self.x = x self.y = y# Function to calculate the manhattan distance between pair of pointsdef 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 pointdef 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 coordinatedef 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 codefind_min_distance() |
Output:
10
Performance Analysis:
- Time Complexity: O(N! * N)
- Auxiliary Space: O(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
