1066. Campus Bikes II

给一系列A的坐标和B的坐标，给每个a找b，使得全局曼哈顿距离最小，曼哈顿距离dist(a, b) = |a.x - a.x| + |b.y - b.y|。和Campus Bikes I 区别在于那道是每个a找最近的b, 贪心。但贪心的结果不一定是全局最优。这是NP-hard问题，想全局最优只有DFS。和之前遇到的哈密尔顿问题类似，用bitmap存下各状态下最优解，state1记录A分配情况，state2记录B使用情况。

代码直接用了这的。

class Solution {
public:
    int minManHaDis(vector<vector<int>> &ws, vector<vector<int>> &bs) {
        int m = ws.size(), n = bs.size();//m <= n based on the question;
        vector<vector<int>> memo(1<<m, vector<int>(1<<n, -1));
        int state1 = 0, state2 = 0;
        int res = dfs(0, ws, state1, bs, state2, memo);
        //cout<<res<<endl;
        return res;
    }
 
private:
    int dfs(int i, vector<vector<int>> &ws, int st1, vector<vector<int>> &bs, int st2, vector<vector<int>> &memo) {
        if(i==ws.size()) return 0;//all the workers are assigned;
        if(memo[st1][st2] != -1) return memo[st1][st2];//calculated;
        int min_dis = INT_MAX;
        for(int j = 0; j < bs.size(); ++j) {//try all the bikes;
            if((st2>>j) & 1) continue;//if the bike is used;
            int one_dis = abs(ws[i][0] - bs[j][0]) + abs(ws[i][1] - bs[j][1]);
            one_dis += dfs(i+1, ws, st1 | (1<<i), bs, st2 | (1<<j), memo);//total dis in this case;
            min_dis = min(min_dis, dis);//min distance;
        }
        return memo[st1][st2] = min_dis;//memorize min distance;
    }
};