package com.fishercoder.solutions;

/**
 * 1066. Campus Bikes II
 *
 * On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.
 * We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.
 * The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
 * Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.
 *
 * Example 1:
 * Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
 * Output: 6
 * Explanation:
 * We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.
 *
 * Example 2:
 * Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
 * Output: 4
 * Explanation:
 * We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1.
 * Both assignments lead to sum of the Manhattan distances as 4.
 *
 * Note:
 * 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
 * All worker and bike locations are distinct.
 * 1 <= workers.length <= bikes.length <= 10
 * */
public class _1066 {
    public static class Solution1 {
        int minSum = Integer.MAX_VALUE;

        public int assignBikes(int[][] workers, int[][] bikes) {
            backtracking(workers, bikes, 0, new boolean[bikes.length], 0);
            return minSum;
        }

        private void backtracking(int[][] workers, int[][] bikes, int workersIndex, boolean[] bikesAssigned, int currentSum) {
            if (workersIndex >= workers.length) {
                minSum = Math.min(minSum, currentSum);
                return;
            }

            if (currentSum > minSum) {
                return;
            }
            
            for (int j = 0; j < bikes.length; j++) {
                if (!bikesAssigned[j]) {
                    bikesAssigned[j] = true;
                    backtracking(workers, bikes, workersIndex + 1, bikesAssigned, currentSum + dist(workers[workersIndex], bikes[j]));
                    bikesAssigned[j] = false;
                }
            }
        }

        private int dist(int[] worker, int[] bike) {
            return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
        }
    }
}

@@ -33,1238 +33,8 @@
 s;%0A%0A
-/**%0A * 1066. Campus Bikes II%0A *%0A * On a campus represented as a 2D grid, there are N workers and M bikes, with N %3C= M. Each worker and bike is a 2D coordinate on this grid.%0A * We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.%0A * The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = %7Cp1.x - p2.x%7C + %7Cp1.y - p2.y%7C.%0A * Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.%0A *%0A * Example 1:%0A * Input: workers = %5B%5B0,0%5D,%5B2,1%5D%5D, bikes = %5B%5B1,2%5D,%5B3,3%5D%5D%0A * Output: 6%0A * Explanation:%0A * We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.%0A *%0A * Example 2:%0A * Input: workers = %5B%5B0,0%5D,%5B1,1%5D,%5B2,0%5D%5D, bikes = %5B%5B1,0%5D,%5B2,2%5D,%5B2,1%5D%5D%0A * Output: 4%0A * Explanation:%0A * We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1.%0A * Both assignments lead to sum of the Manhattan distances as 4.%0A *%0A * Note:%0A * 0 %3C= workers%5Bi%5D%5B0%5D, workers%5Bi%5D%5B1%5D, bikes%5Bi%5D%5B0%5D, bikes%5Bi%5D%5B1%5D %3C 1000%0A * All worker and bike locations are distinct.%0A * 1 %3C= workers.length %3C= bikes.length %3C= 10%0A * */%0A
 publ
@@ -653,28 +653,16 @@
       %7D%0A
-            
 %0A       

refactor 1066