某岛

… : "…アッカリ～ン . .. . " .. .

March 15, 2011

URAL 1519. Formula 1

Brief description :

一条回路问题，给定一个 n × m 的有障碍地图，求用一条回路遍历所有格子的方案数。
（1 <= n, m <= 12 ...）

Analyse :

延续之前的思路，发现不行。例如下图：

这两种状态现在必须要区别对待，需要记录插头之间的匹配情况，发现符合括号结构。
这里仍然用一个整形 int 变量，用低位表示插头的存在性，高位说明插头的类型，。

继续推。。

依然是分前面的三种情况讨论，其中插头的左移右移不动（插头的类型保持不变）还有生成一组新插头（可以确定是这样: ‘( )’）两种差别并不大，情况发生大变化的是合并。

首先，'( )’ 这种情况是不再可以随意合并的。（会形成一个回路，是限卡，只在最后的一行（如果最后一行不是全是石头的话）的时侯可以发动一次。），接着 ‘) (‘ 情况可以直接合并，不会出甚么大的乱子。

那么对于剩下的两种 ‘( (‘ 还有 ‘) )’ 呢？… 请记住下面的口诀：

左插头吃左插头会把右边的插头所对应的那个右插头变成左插头 ..#>.
右插头吃右插头会把左边的插头所对应的那个左插头变成右插头 …….

.
….
请吧。

#include 
#include 
#include 
#include 
using namespace std;   //15511 ...
const int hh = 12, ww = 12, _W = 16, ll = 15511;

long long f[2][ll], d; map H;
int L[ll], O[hh], h, w, up, l;
int s, o, n, m, p, q; int i; 


#define _Pl (s & (1 << l))
#define _Pr (s & (1 << r))
#define _Pi (s & (1 << i))
// Check Plug.

#define _Ol (o & (1 << l))
#define _Or (o & (1 << r))
// Check Obstacle...

#define _Tl (s & (1 << l + _W))
#define _Tr (s & (1 << r + _W))
#define _Ti (s & (1 << i + _W))
// Return Plug Type ..


#define _Sl s ^= 1 << l
#define _Sr s ^= 1 << r
// Reset Plug ..

#define _Cl s ^= 1 << (l + _W)
#define _Cr s ^= 1 << (r + _W)
#define _Ci s ^= 1 << (i + _W)
// Change Brace Structure


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

void eatLeft(int i){
	int An = 0;
	for (i--;;i--){
		if (!_Pi) continue;
		if (_Ti) An++;
		else {if (An==0){_Ci; return;} An--;}
	}
}
void eatRight(int i){
	int An = 0;
	for (i++;;i++){
		if (!_Pi) continue;
		if (!_Ti) An++;
		else {if (An==0){_Ci; return;} An--;}
	}
}



void dfs(int l){
	if (l == m){
		f[p][H[s]] += d;
	}
	else {
		int r = l + 1;
		
		if (_Ol){
			dfs(r);
			return;
		}
		
		int c = s;
		
		if (_Pl){
			// 0: Stable ..
			dfs(r);
			
			if (_Tl){  
				// 2: Move_Right with ')' . ..
				while (!_Pr && !_Or){ 
					_Sl; _Cl; _Sr; _Cr; dfs(++r); s = c;
				}
				
				// 4: Merge with '))'
				if (_Pr){
					if (_Tr){
						eatLeft(l); _Sl; _Cl; _Sr; _Cr; dfs(r+1); s = c;
					}
					// 4: Merge with ')('
					else {
						_Sl; _Cl; _Sr; dfs(r+1); s = c;
					}
				}
			}
			else {
				// 2: Move_Right with '(' . ..
				while (!_Pr && !_Or){
					_Sl; _Sr; dfs(++r); s = c;
				}
				
				// 4: Merge with '(('
				if (!_Or){
					if (!_Tr){
						eatRight(r); _Sl; _Sr; dfs(r+1); s = c;
					}
					// 4 Merge with '()'
					else {
						//!..#>..#>.f
						if (i + 1 == h && r + 1 == m && countBits(s)==2){
							f[p][0] += d; 
						}
						
					}
				}
			}
			
		}
		else {
			// 3: Bown a pair of new plug . ...
			while (!_Pr && !_Or){
				_Sl; _Sr; _Cr; dfs(++r); s = c;
			}
			
			// 1 Move_Left
			if (!_Or){
				if (_Tr) {_Sl; _Cl; _Sr; _Cr; dfs(r+1); s = c;}
				else {_Sl; _Sr; dfs(r+1); s = c;}
			}
		}
	}
}


void scan(int i, int ln, int rn){
	while (!_Pi) i++;
	
	if (i==w) {
		H[s ^ up] = l;
		L[l++] = s ^ up;
	}
	else {
		if (ln < n) scan(i+1, ln+1, rn);
		if (rn < ln) {_Ci; scan(i+1, ln, rn+1); _Ci;}
	}
}

void init(){
    scanf("%d%d", &h, &w); 
    
	l = 0, up = 1 << w, H.clear();
	for (int i = 0; i < up; i++){
		n = countBits(i);
		if ((n&1)==0){s = i | up, n >>= 1, scan(0, 0, 0);}
	}
	
	char t;
	for (int i = 0; i < h; i++){
		O[i] = 1;
		for (int j = 0; j < w; j++){
			scanf(" %c", &t); O[i] <<= 1;
			if (t!='.') O[i] += 1;
		}
	}
	
	while (O[h-1] == 2 * up - 1) h--;	
	memset(f, 0, sizeof(f));
}



void solve(){
	i = 0;
	while (O[i] == 2 * up - 1) i++;
	f[q = 0][s = 0] = d = 1; p = 1, m = w, o = O[i]; 
	while (o & (1 << (m - 1))) m--;
	dfs(0);
	
	
	for (i ++; i < h; i ++){
		q = p, p = 1 - p, m = w, o = O[i];
		memset(f[p], 0, sizeof(f[p]));
		while (o & (1 << (m - 1))) m--;
		for (int ii = 0; ii < l; ii ++){
			if (f[q][ii] && !(L[ii] & o))
				d = f[q][ii], s = L[ii], dfs(0);
		}
	}
}


int main(){        
    //freopen("in.txt", "r", stdin);
	init();  solve(); //patch();
	cout << f[p][0] << endl;
}

#include 
#include 
#include 
using namespace std;
const int hh = 12, ww = 12, _W = 16, MaxH = 15511;
bool O[hh+1][ww+1]; bool A, B, X, Y; int h, w, l, s;
long long ans, d;

struct hashTable {
	int state[MaxH], head[MaxH], next[MaxH], sz;
	long long key[MaxH];
	
	inline void clear() {
		sz = 0;
		memset(head, -1, sizeof(head));
	}
	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;
		next[sz] = head[x];
		head[x] = sz++;
	}
} H[2] , *src , *des;



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;iclear(), des->insert(0);
	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--;
		
		
		for (int j = 0; j < w; j ++){
			
			if (O[i][j]) continue;
			
			swap(src, des), des->clear();			
			
			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));				

				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 (i + 1 == h && j + 1 == w && countBits(s)==2)
									ans += d;
							}
							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(){        
    //freopen("in.txt", "r", stdin);
	init();  solve();
	cout << ans << endl;
}



/*
 
 12 12
 ............
 ............
 ............
 ............
 ............
 ............
 ............
 ............
 ............
 ............
 ............
 ............
 
 1076226888605605706
 
 */