Brief description :

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

Analyse :

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

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

继续推。。

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

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

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

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

.
….
请吧。

#include 
#include 
#include 
#include 

#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
 
 */

Further discussion :

请注意数据包含了一些要忽略的空格，并小心外面围了几圈全是石头的情况。

External link :

http://acm.timus.ru/problem.aspx?space=1&num=1519
http://blog.sina.com.cn/s/blog_51cea4040100gmky.html

Posted by xiaodao
Category: 日常