SHARE
TWEET

Crippled King bruteforce

a guest Apr 6th, 2016 27 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
  4.  
  5. vector<int> components[10];
  6. int p[30];
  7.  
  8. map< pair< int, vector<int> >, unsigned long long> memo;
  9.  
  10. int find(int x) {
  11.     if (p[x] == x) return x;
  12.     return p[x]=find(p[x]);
  13. }
  14.  
  15. void link(int a, int b) {
  16.     int x = find(a), y = find(b);
  17.     if (x < y) swap(x,y);
  18.     p[x]=y;
  19. }
  20.  
  21. unsigned long long rec(int row) {
  22.     if (row == 8) return 1;
  23.  
  24.     const vector<int> &this_comp = components[row];
  25.     vector<int> &next_comp = components[row+1];
  26.  
  27.     unsigned long long &ans = memo[{row, this_comp}];
  28.     if (ans == 0) {
  29.         for (int new_row = 1; new_row < (1<<8); new_row++) {
  30.             REP(i,20) p[i] = i;
  31.             REP(i,8) next_comp[i] = 5+i;
  32.  
  33.             for (int i = 0; i < 8; i++) if (new_row & (1<<i)) {
  34.                 for (int dx = -1; dx <= 1; dx++) {
  35.                     // SWITCH THESE TWO LINES TO GET ORIGINAL CRIPPLED KING:
  36.                     if (dx == 0) continue;
  37.                     //if (dx == 1) continue;
  38.  
  39.                     int nx = i + dx;
  40.                     if (nx >= 0 && nx < 8 && this_comp[nx]) {
  41.                         link(this_comp[nx], next_comp[i]);
  42.                     }
  43.                 }
  44.  
  45.                 if (i > 0 && (new_row & (1<<(i-1))) ) {
  46.                     link(next_comp[i-1], next_comp[i]);
  47.                 }
  48.             }
  49.  
  50.             bool seen1 = false;
  51.             REP(i, 8) {
  52.                 next_comp[i] = find(next_comp[i]);
  53.                 if (next_comp[i] == 1) seen1 = true;
  54.             }
  55.  
  56.             if (seen1) {
  57.                 vector<int> rem;
  58.                 REP(i, 8) if (new_row & (1<<i)) rem.push_back(next_comp[i]);
  59.                 sort(rem.begin(), rem.end());
  60.                 int rem_count = unique(rem.begin(), rem.end()) - rem.begin();
  61.                 REP(i,8) {
  62.                     if (new_row & (1<<i)) next_comp[i] = (lower_bound(rem.begin(), rem.begin() + rem_count, next_comp[i]) - rem.begin()) + 1;
  63.                     else next_comp[i] = 0;
  64.                 }
  65.  
  66.                 ans += rec(row+1);
  67.             }
  68.         }
  69.     }
  70.  
  71.     return ans;
  72. }
  73.  
  74. int main() {
  75.     REP(i,10) components[i].resize(8);
  76.     REP(i,8) components[0][i] = 1;
  77.  
  78.     unsigned long long successful_crossings = rec(0);
  79.     printf("Successful crossings: %llu out of 18446744073709551616\n", successful_crossings);
  80. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top