某岛

… : "…アッカリ～ン . .. . " .. .
August 20, 2015

ProjectEuler 393. Migrating ants

https://projecteuler.net/problem=393

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int hh = 12, ww = 12, _W = 15, MaxH = 10 * 15511;
bool O[hh+1][ww+1]; int A, B, X, Y; int h, w, l, s;
long long ans, d;

struct hashTable {
long long key[MaxH];

inline void clear() {
sz = 0;
}
inline void insert(int s) {
int x = s % MaxH;
for ( int it = head[x] ; it != -1 ; it = next[it] ) {
if ( state[it] == s ) {
key[it] += d;
return;
}
}
state[sz] = s, key[sz] = d;
}
} H[2] , *src , *des;

int n;

inline int countBits(int x){
x = (x & 0x00005555) + ((x & 0x0000aaaa) >> 1);
x = (x & 0x00003333) + ((x & 0x0000cccc) >> 2);
x = (x & 0x00000f0f) + ((x & 0x0000f0f0) >> 4);
x = (x & 0x000000ff) + ((x & 0x0000ff00) >> 8);
return x;
}

int eatLeft(int s, int i){
int An = 0;
for (i--;;i--){
if (!(s & (1 << i))) continue;
if (s & (1 << _W + i)) An++;
else {if (An==0){s ^= 1 << (_W + i); return s;} An--;}
}
}
int eatRight(int s, int i){
int An = 0;
for (i++;;i++){
if (!(s & (1 << i))) continue;
if (!(s & (1 << _W + i))) An++;
else {if (An==0){s ^= 1 << (_W + i); return s;} An--;}
}
}

bool _O(){
for (int i=0;i<w;i++)
if (!O[h-1][i]) return false;
return true;
}

void init(){

h = w = n;

for (int i=0;i<h;i++)
for (int j=0;j<w;j++)
O[i][j] = false;

while (_O()) h--;

for (int i=0;i<h;i++)
O[h][i] = O[i][w] = true;

}

void solve(){

src = H, des = src + 1, d = 1;
des->clear(), des->insert(0); src->clear();
ans = 0;

int _w = w;

for (int i = 0; i < h; i ++){

for (int j = 0; j < src->sz; j ++)
des->state[j] <<= 1;

w = _w;

while (O[i][w-1]) w--;

//  cout << w << " " << i << endl;

for (int j = 0; j < w; j ++){

if (O[i][j]) continue;

swap(src, des), des->clear();

// cout << " " << j << endl;

for (int k = 0; k < src->sz; k ++){
s = src->state[k], d = src->key[k];
A = s & (1 << j), B = s & (1 << (j+1));

//       cout << "  " << k << " " << src->sz << endl;

if (!A && !B){
if (!O[i+1][j] && !O[i][j+1]) des->insert(s ^ (3 << j | 1 <<( _W + j + 1)));
}
else{

X = s & (1 << (_W + j)), Y = s & (1 << (_W + j + 1));

if (A && B){

if (X){
if (Y){ //'))'
des->insert(eatLeft(s, j) ^ (3 << j | 3 << _W + j));
}
else { //')('
des->insert(s ^ (3 << j | 1 << _W + j));
}
}
else {
if (Y){ //'()'                            if (Y){ //'()'

//  ans += d;

d *= 2;

if (i + 1 == h && j + 1 == w && countBits(s)==2) ans += d;

//   d *= 2;

// if (

des->insert(s ^ (3 << j) ^ X ^ Y);

d /= 2;

}
else { //'(('
des->insert(eatRight(s, j+1) ^ (3 << j));
}
}

}
else {
if (A){
if (!O[i+1][j]) des->insert(s);

if (!O[i][j+1]) {
if (X) des->insert(s ^ (3 << j | 3 << (_W + j)));
else des->insert(s ^ (3 << j));
}
}
else {
if (!O[i][j+1]) des->insert(s);
if (!O[i+1][j]) {
if (Y) des->insert(s ^ (3 << j | 3 << (_W + j)));
else des->insert(s ^ (3 << j));
}
}
}
}

}
}
}
}

int main(){

#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif

//freopen("in.txt", "r", stdin);
while (cin >> n){
init(); ans = 0;  solve();
cout << ans << endl;
}
}