Crippled King bruteforce

#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);
}