algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (2415B)


      1 #include <iostream>
      2 #include <climits>
      3 #include <bitset>
      4 #include <vector>
      5 
      6 // - thoughts:
      7 //     - there are objects in a room that have to be placed in a container
      8 //     - the girl can only carry at most two objects at a time
      9 //     - container can't move
     10 //     - if an object is picked up, it must be moved directly to the handbag, not pickup / set down
     11 //     - cover distance between two objects in time equal to squared length of the segment connecting the objects
     12 //         - euclidean distance squared
     13 //     - girl starts at the handbag
     14 //     - find operations that minimizes time to get all objects in container
     15 
     16 // this feels dp.
     17 
     18 // what's the state?
     19     // s(visited, holding, position)
     20         // where visited is a bitmask
     21             // at most 24 bits
     22 
     23 using namespace std;
     24 
     25 int distance(int x1,int y1,int x2,int y2) {
     26     return ((x2-x1) * (x2-x1)) + ((y2-y1) * (y2-y1));
     27 }
     28 
     29 int solve(vector<int>& xVals, vector<int>& yVals, bitset<24> current, int holding, int x, int y, int cx, int cy, vector<int>& memo) {
     30 
     31     if(holding == 0 && memo[current.to_ulong()] != -1) {
     32         return memo[current.to_ulong()];
     33     }
     34 
     35     int shortest = INT_MAX;
     36     bool found = false;
     37 
     38     if(holding < 2) {
     39         for(int i = 0; i < xVals.size(); ++i) {
     40             if(current[i] == 0) {
     41                 bitset<24> updated = current;
     42                 updated[i] = 1;
     43                 int dist = distance(x,y,xVals[i], yVals[i]);
     44                 int cv = solve(xVals,yVals,updated, holding+1, xVals[i],yVals[i], cx, cy, memo);
     45                 shortest = min(cv+dist,shortest);
     46                 found = true;
     47             }
     48         }
     49     }
     50     
     51     if(holding > 0) {
     52         int dist = distance(x,y,cx,cy);
     53         int cv = solve(xVals,yVals,current, 0, cx,cy, cx, cy, memo);
     54         shortest = min(cv+dist,shortest);
     55         found = true;
     56     }
     57 
     58     if(!found) {
     59         return 0; // done
     60     }
     61 
     62     if(holding == 0) {
     63         memo[current.to_ulong()] = shortest;
     64     }
     65 
     66     return shortest;
     67 }
     68 
     69 int main() {
     70     int n, hx, hy, cx, cy = 0;
     71 
     72     cin >> hx;
     73     cin >> hy;
     74 
     75     cin >> n;
     76 
     77     vector<int> xVals{};
     78     vector<int> yVals{};
     79 
     80     for(int i = 0; i < n; ++i) {
     81         cin >> cx;
     82         cin >> cy;
     83         xVals.push_back(cx);
     84         yVals.push_back(cy);
     85     }
     86     
     87     bitset<24> current {};
     88 
     89     vector<int> memo(1 << n, -1);
     90 
     91     cout << solve(xVals,yVals,current, 0, hx,hy, hx, hy, memo) << endl;
     92 }