Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define REP(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
- vector<int> components[10];
- int p[30];
- map< pair< int, vector<int> >, unsigned long long> memo;
- int find(int x) {
- if (p[x] == x) return x;
- return p[x]=find(p[x]);
- }
- void link(int a, int b) {
- int x = find(a), y = find(b);
- if (x < y) swap(x,y);
- p[x]=y;
- }
- unsigned long long rec(int row) {
- if (row == 8) return 1;
- const vector<int> &this_comp = components[row];
- vector<int> &next_comp = components[row+1];
- unsigned long long &ans = memo[{row, this_comp}];
- if (ans == 0) {
- for (int new_row = 1; new_row < (1<<8); new_row++) {
- REP(i,20) p[i] = i;
- REP(i,8) next_comp[i] = 5+i;
- for (int i = 0; i < 8; i++) if (new_row & (1<<i)) {
- for (int dx = -1; dx <= 1; dx++) {
- // SWITCH THESE TWO LINES TO GET ORIGINAL CRIPPLED KING:
- if (dx == 0) continue;
- //if (dx == 1) continue;
- int nx = i + dx;
- if (nx >= 0 && nx < 8 && this_comp[nx]) {
- link(this_comp[nx], next_comp[i]);
- }
- }
- if (i > 0 && (new_row & (1<<(i-1))) ) {
- link(next_comp[i-1], next_comp[i]);
- }
- }
- bool seen1 = false;
- REP(i, 8) {
- next_comp[i] = find(next_comp[i]);
- if (next_comp[i] == 1) seen1 = true;
- }
- if (seen1) {
- vector<int> rem;
- REP(i, 8) if (new_row & (1<<i)) rem.push_back(next_comp[i]);
- sort(rem.begin(), rem.end());
- int rem_count = unique(rem.begin(), rem.end()) - rem.begin();
- REP(i,8) {
- if (new_row & (1<<i)) next_comp[i] = (lower_bound(rem.begin(), rem.begin() + rem_count, next_comp[i]) - rem.begin()) + 1;
- else next_comp[i] = 0;
- }
- ans += rec(row+1);
- }
- }
- }
- return ans;
- }
- int main() {
- REP(i,10) components[i].resize(8);
- REP(i,8) components[0][i] = 1;
- unsigned long long successful_crossings = rec(0);
- printf("Successful crossings: %llu out of 18446744073709551616\n", successful_crossings);
- }
Add Comment
Please, Sign In to add comment