leetcode 1066 - Campus Bikes II

https://leetcode.com/problems/campus-bikes-ii/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
int result = INT_MAX;

int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
int size = 1 << bikes.size();
vector<int> dp(size, -1);

return backtrack(workers, bikes, 0, dp, 0);
}

int backtrack(vector<vector<int>>& workers, vector<vector<int>>& bikes,
int i, vector<int> &dp, int used) {
if (i == workers.size()) return 0;

if (dp[used] != -1) return dp[used];

int min_dist = INT_MAX;

for (int p = 0; p < bikes.size(); p++) {
if (used & (1<<p)) continue;

used |= (1<<p);
int dist = backtrack(workers, bikes, i+1, dp, used) + distance(workers[i], bikes[p]);
min_dist = min(min_dist, dist);
used &= ~(1<<p);
}

dp[used] = min_dist;
return min_dist;
}

int distance(vector<int> &worker, vector<int> &bike) {
return abs(worker[0]-bike[0]) + abs(worker[1]-bike[1]);
}
};