Minimum distance to collect coins and place them in House
Given an m*n matrix that contains character ‘B’ to represent the boy’s initial position, ‘H’ represents the house’s position, ‘C’ represents the position of coins, and ‘.’ represents empty cells, the task is to find the minimum distance (i.e. minimum moves) for the boy to collect all the coins and place them inside the house one by one. The boy can only pick up one coin at a time and can move in four directions: up, down, left, and right, to the adjacent cell.
Example:
Input: m = 5, n = 7, H = {2,2}, B = {4,4}, C : {{3,0}, {2,5}}
Output: 12
Explanation:Input: m = 1, n = 3, H = {0,1}, B = {0,0}, C = {{0,2}}
Output: 3
Minimum distance to collect coins and place them in House using Manhattan distance:
The boy needs to visit all the coins and, for each coin, boy must travel from the coin’s position to the house’s position twice, except for the first coin. For the first coin, the boy travels from his initial position to the coin’s position and then to the house’s position. So, to minimize the total distance traveled, our aim is to choose the first coin in such a way that the overall distance is minimized.
Step-by-step approach:
- Calculate the total distance from the house to all coins by summing up the Manhattan distances between the house and each coin.
- Check, if the house and the boy are already at the same position, return 2 * total distance (since the boy picks up and drops off the coins at the same location).
- Iterate through each coin and calculate:
- Calculate Manhattan distance from the boy to the coin (diffBoy2Coin).
- The Manhattan distance from the house to the coin (diffHouse2Coin).
- Update the result with the minimum possible distance: 2 * total distance + diffBoy2Coin – diffHouse2Coin
- Finally, return the result
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to calculate the minimum distance int solve( int m, int n, vector< int >& house, vector< int >& boy, vector<vector< int > >& coins) { // To store the total distance from the // house to all coins int sum = 0; // Calculate the total distance from the // house to all coins for ( auto coin : coins) { sum += abs (house[0] - coin[0]) + abs (house[1] - coin[1]); } // If the house and the boy are at the // same position, return double the sum if (house[0] == boy[0] && house[1] == boy[1]) return 2 * sum; int result = INT_MAX; // Iterate through all the coins to find // the optimal starting coin for ( int i = 0; i < coins.size(); i++) { // Calculate the Manhattan distance // between the boy and the current coin int diffBoy2Coin = abs (boy[0] - coins[i][0]) + abs (boy[1] - coins[i][1]); // Calculate the Manhattan distance // between the house and the current coin int diffHouse2Coin = abs (house[0] - coins[i][0]) + abs (house[1] - coins[i][1]); // Update the result with the minimum // possible distance result = min(result, 2 * sum + diffBoy2Coin - diffHouse2Coin); } return result; } // Driver code int main() { int m = 5, n = 7; // House coordinates vector< int > H = { 2, 2 }; // Boy's initial coordinates vector< int > B = { 4, 4 }; // Coin coordinates vector<vector< int > > C = { { 3, 0 }, { 2, 5 } }; // Call the solve function and // print the result cout << solve(m, n, H, B, C); return 0; } |
Java
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class CoinCollection { // Function to calculate the minimum distance public static int solve( int m, int n, List<Integer> house, List<Integer> boy, List<List<Integer> > coins) { // To store the total distance from the house to all // coins int sum = 0 ; // Calculate the total distance from the house to // all coins for (List<Integer> coin : coins) { sum += Math.abs(house.get( 0 ) - coin.get( 0 )) + Math.abs(house.get( 1 ) - coin.get( 1 )); } // If the house and the boy are at the same // position, return double the sum if (house.get( 0 ).equals(boy.get( 0 )) && house.get( 1 ).equals(boy.get( 1 ))) return 2 * sum; int result = Integer.MAX_VALUE; // Iterate through all the coins to find the optimal // starting coin for ( int i = 0 ; i < coins.size(); i++) { // Calculate the Manhattan distance between the // boy and the current coin int diffBoy2Coin = Math.abs(boy.get( 0 ) - coins.get(i).get( 0 )) + Math.abs(boy.get( 1 ) - coins.get(i).get( 1 )); // Calculate the Manhattan distance between the // house and the current coin int diffHouse2Coin = Math.abs(house.get( 0 ) - coins.get(i).get( 0 )) + Math.abs(house.get( 1 ) - coins.get(i).get( 1 )); // Update the result with the minimum possible // distance result = Math.min(result, 2 * sum + diffBoy2Coin - diffHouse2Coin); } return result; } public static void main(String[] args) { int m = 5 , n = 7 ; // House coordinates List<Integer> H = Arrays.asList( 2 , 2 ); // Boy's initial coordinates List<Integer> B = Arrays.asList( 4 , 4 ); // Coin coordinates List<List<Integer> > C = new ArrayList<>(); C.add(Arrays.asList( 3 , 0 )); C.add(Arrays.asList( 2 , 5 )); // Call the solve function and print the result System.out.println(solve(m, n, H, B, C)); } } |
Python3
def solve(m, n, house, boy, coins): # To store the total distance from the house to all coins sum = 0 # Calculate the total distance from the house to all coins for coin in coins: sum + = abs (house[ 0 ] - coin[ 0 ]) + abs (house[ 1 ] - coin[ 1 ]) # If the house and the boy are at the same position, return double the sum if house[ 0 ] = = boy[ 0 ] and house[ 1 ] = = boy[ 1 ]: return 2 * sum result = float ( 'inf' ) # Iterate through all the coins to find the optimal starting coin for i in range ( len (coins)): # Calculate the Manhattan distance between the boy and the current coin diffBoy2Coin = abs (boy[ 0 ] - coins[i][ 0 ]) + abs (boy[ 1 ] - coins[i][ 1 ]) # Calculate the Manhattan distance between the house and the current coin diffHouse2Coin = abs (house[ 0 ] - coins[i][ 0 ]) + abs (house[ 1 ] - coins[i][ 1 ]) # Update the result with the minimum possible distance result = min (result, 2 * sum + diffBoy2Coin - diffHouse2Coin) return result # Driver code m = 5 n = 7 # House coordinates H = [ 2 , 2 ] # Boy's initial coordinates B = [ 4 , 4 ] # Coin coordinates C = [[ 3 , 0 ], [ 2 , 5 ]] # Call the solve function and print the result print (solve(m, n, H, B, C)) |
C#
using System; using System.Collections.Generic; class GFG { // Function to calculate the minimum distance static int Solve( int m, int n, List< int > house, List< int > boy, List<List< int >> coins) { int sum = 0; // Calculate the total distance from house to all coins foreach ( var coin in coins) { sum += Math.Abs(house[0] - coin[0]) + Math.Abs(house[1] - coin[1]); } // If the house and the boy are at the // same position, return double the sum if (house[0] == boy[0] && house[1] == boy[1]) return 2 * sum; int result = int .MaxValue; // Iterate through all the coins to find // the optimal starting coin for ( int i = 0; i < coins.Count; i++) { // Calculate the Manhattan distance // between the boy and the current coin int diffBoy2Coin = Math.Abs(boy[0] - coins[i][0]) + Math.Abs(boy[1] - coins[i][1]); // Calculate the Manhattan distance // between the house and current coin int diffHouse2Coin = Math.Abs(house[0] - coins[i][0]) + Math.Abs(house[1] - coins[i][1]); // Update the result with minimum possible distance result = Math.Min(result, 2 * sum + diffBoy2Coin - diffHouse2Coin); } return result; } // Driver code static void Main() { int m = 5, n = 7; // House coordinates List< int > H = new List< int > { 2, 2 }; // Boy's initial coordinates List< int > B = new List< int > { 4, 4 }; // Coin coordinates List<List< int >> C = new List<List< int >> { new List< int > { 3, 0 }, new List< int > { 2, 5 } }; // Call the Solve function and print the result Console.WriteLine(Solve(m, n, H, B, C)); } } |
Javascript
// Javascript code for the above approach // Function to calculate the minimum distance function solve(m, n, house, boy, coins) { // To store the total distance from the // house to all coins let sum = 0; // Calculate the total distance from the // house to all coins for (let coin of coins) { sum += Math.abs(house[0] - coin[0]) + Math.abs(house[1] - coin[1]); } // If the house and the boy are at the // same position, return double the sum if (house[0] === boy[0] && house[1] === boy[1]) { return 2 * sum; } let result = Number.MAX_SAFE_INTEGER; // Iterate through all the coins to find // the optimal starting coin for (let i = 0; i < coins.length; i++) { // Calculate the Manhattan distance // between the boy and the current coin let diffBoy2Coin = Math.abs(boy[0] - coins[i][0]) + Math.abs(boy[1] - coins[i][1]); // Calculate the Manhattan distance // between the house and the current coin let diffHouse2Coin = Math.abs(house[0] - coins[i][0]) + Math.abs(house[1] - coins[i][1]); // Update the result with the minimum // possible distance result = Math.min(result, 2 * sum + diffBoy2Coin - diffHouse2Coin); } return result; } // Driver code let m = 5, n = 7; // House coordinates let H = [2, 2]; // Boy's initial coordinates let B = [4, 4]; // Coin coordinates let C = [[3, 0], [2, 5]]; // Call the solve function and // print the result console.log(solve(m, n, H, B, C)); |
12
Time Complexity: O(|C|), where |C| is coin size.
Auxiliary Space: O(1)
Contact Us