Brief description :

多条回路问题，给定一个 n × m 的有障碍地图，求用若干条回路覆盖所有格子的有多少种方案。
（1 <= n, m <= 11 ...）

Analyse :

设计状态，试试看能不能逐行转移？f[i][s] 表示前 i 层，第 i 层状态为 s 的方案数，s 的每一位表示此处是否有插头，且插头一定是成对出现，是偶数，接下来分析状态转移，先考虑没有障碍的情况，我们以 m = 4 的一个情况做例子。

• 这个位置是有插头的。
  • 不动。
  • 开始向右扫描，如果右侧的位置是一组零零零零，那么插头右移。0100，0010，0001 这样。。
  • 撞墙的时侯遇到一个同伴，那么同它合体。例如 1001，合体以后形成 0000。
• 这个位置没有插头。
  • 向右扫描，如果右侧的几个位置也一直是一组零零零零，那么必须（以确保完全覆盖）生成一组新插头。1100，1010，1001。
  • 撞墙的时侯遇到一个插头，那么需要把这个插头向左引向此处。

总的来说一共也只有：生成一组新插头、插头向两边移动或者不变、合并两个插头这三种情况而已。这之后在加上判断障碍的部分就可以了。

#include 
#include 
#include 
using namespace std;

const int hh = 11, ss = 1 << hh;
long long f[2][ss], d;
int L[ss], h, w, up;
int s, o, p, q;


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

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

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

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


inline bool isLegal(int x){
    return (countBits(x) & 1) == 0;
}

void dfs(int l){
	if (l == w){
		f[p][s] += d;
	}
	else {		
		int r = l + 1;
		
		if (_Ol){
			dfs(r);
			return;
		}
		
		
		if (_Pl){
			// 位置不变..
			dfs(r);
			
			// 插头右移 ..
			_Sl;
			while (!_Pr && !_Or){
				_Sr; dfs(r+1); _Sr;
				r++;
			}
			
			// 插头合并 ...
			if (_Pr){
				_Sr; dfs(r+1); _Sr;
			}
			_Sl;
		}
		else {
			_Sl;
			// 生成一组新插头. ...
			while (!_Pr && !_Or){
				_Sr; dfs(r+1); _Sr;
				r++;
			}
			
			// 插头左移 ..
			if (_Pr){
				_Sr; dfs(r+1); _Sr;
			}
			_Sl;
		}
	}
}


void solve(){
	f[p = 0][s = 0] = 1;
	
	int t;
	for (int i = 0; i < h; i ++){
		q = p, p = 1 - p, o = 1;
		memset(f[p], 0, sizeof(f[p]));
		
		for (int j = 0; j < w; j++)
			scanf("%d", &t), o = (o << 1)  + (t == 0); 
		
		for (int ii = 0; ii < up; ii ++){
			s = L[ii];
			if (f[q][s] &&  !(s & o))
				d = f[q][s], dfs(0);
		}
	}
}

void init(){
    scanf("%d%d", &h, &w); 
    
	int t = 1 << w; up = 0;
    for (int i = 0; i < t; i++)
        if (isLegal(i)) L[up++] = i, 
	memset(f, 0, sizeof(f));
}


int main(){        
    freopen("in.txt", "r", stdin);
    int T; cin >> T;
    for (int i=1;i<=T;i++){
        init();  solve();
        printf("Case %d: There are %lld ways to eat the trees.\n", i, f[p][0]);
        //printf("Case %d: There are %I64d ways to eat the trees.\n", i, f[p][0]);
    }
}

#include 
#include 
#include 
using namespace std;

const int hh = 11, ss = 1 << hh, MaxH = ss / 2;
bool O[hh+1][hh+1], lt, up; 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++;
	}
	inline long long search(int s){
		int x = s % MaxH;
		for ( int it = head[x] ; it != -1 ; it = next[it])
			if ( state[it] == s ) return key[it];
		return 0;
	}
} H[2] , *src , *des;



void patch(){
	for (int i=0;isz;i++)
		cout << des->state[i] << "," << des->key[i] << " ";
	cout << endl;
}


void solve(){
	src = H, des = src + 1, d = 1;
	des->clear(), des->insert(0);
	
	for (int i = 0; i < h; i ++){
		
		
		for (int j = 0; j < src->sz; j ++)
			des->state[j] <<= 1;
		
		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];
				lt = s & (1 << j), up = s & (1 << (j+1));
				
				//if (lt != up) des->insert(s, d);
				//des->insert(s ^ (3 << j), d);
				
				if (!lt && !up){
					if (!O[i+1][j] && !O[i][j+1]) des->insert(s ^ (3 << j));
				}
				else if (lt && up){
					des->insert(s ^ (3 << j));
				}
				else {
					if (lt){
						if (!O[i+1][j]) des->insert(s);
						if (!O[i][j+1]) des->insert(s ^ (3 << j));
					}
					else {
						if (!O[i][j+1]) des->insert(s);
						if (!O[i+1][j]) des->insert(s ^ (3 << j));
					}
				}
			}
			
			//patch();
		}
		
		
		
		
	}
	
	ans = des->search(0);
}


void init(){
    scanf("%d%d", &h, &w); 
	l = (1 << (w+1)) - 1;
	
	int t;
	for (int i=0;i> T;
    for (int i=1;i<=T;i++){
        init();  solve();
        //printf("Case %d: There are %lld ways to eat the trees.\n", i, ans);
        printf("Case %d: There are %I64d ways to eat the trees.\n", i, ans);
    }
}

Further discussion :

第 90 行附近，障碍一开始的时侯赋值1，这样往后左移的过程可以形成一堵墙，这样 DFS 里面可以省略许多判断 r < w 句子。 15 ms 还可以的样子... 嗯嗯。

External link :

http://acm.hdu.edu.cn/showproblem.php?pid=1693
http://blog.huang-wei.com/2008/08/24/hdu-1693-eat-the-trees/
http://hi.baidu.com/fqq11679/blog/item/423bcd4a3d956bf983025c6d.html

Posted by xiaodao
Category: 日常