树（tree）

树（tree）

题目描述

 

小明正在研究一种砍树游戏。一开始在W列H行的方格上，每一个格子都长着一颗树，格子的行从北到南依次编号，格子的列从西到东依次编号。

小明会砍倒一些树，每砍倒一颗树，树会占据这个格子和它倒向方向的相邻格子。例如：格子(r,c)的树向南倒下，则占据(r,c)和(r+1,c)两个格子。

砍树游戏的规则是：

*树只能向南或向东2个方向倒。

*树不能倒向方格外面。例如最后一列的树不能向东倒。

*不能有2颗砍倒的树占据同一个格子。

在每颗树上写有一个字母:S或E，分别表示南和东，小明砍树时会优先考虑这个方向。例如：小明碰到树上字母是 S 时，会首先看能不能向南砍倒树。

游戏中小明将从第 1 行开始，从左到右依次走到每一格；再第 2 行开始，从左到右依次砍树；…，直到最后一行。在每一格按照下面的算法砍树：

1、判断这格是否有砍倒的树占据?如果是，不砍树，走到下一格去。

2、判断是否可以按照树上字母的方向砍倒树？如果是，朝这个方向砍倒树，走到下一格去。

3、判断是否可以朝另外一个方向砍倒树？如果是，朝这个方向砍倒树，走到下一格去。

4、直接走到下一格去。

例如：一个 4*3 的局面

SEEE

ESSS

EESS

可砍倒 5 颗树，用 1,2,3,4,5 表示依次砍倒的树，形状如下：

1223

1453

_45_

现在给定 W 和 H，由于每个格子可以是 S 或 E，因此有 2^(W*H)种可能的开始局面。计算如果你玩遍所有的 2^(W*H)种开始局面，总共可以砍倒多少颗树？答案可能太大，输出模M的值。

---

solution

发现w只有7，似乎很像状压

那我们就压起来

令f[i][S][j]表示我砍了前i行树，第i行的树被砍的状态为S，一共砍了j棵树的贴字母的方案数

其中状态S为0表示横着砍或不砍（不影响下一行）

为1表示向下砍（影响下一行）

我们用主动转移，这样不用跑满。

转移比较麻烦

//S 状态 c数量 别问我为什么叫这个，我乱取的
if(x.S&(1<<k-1))dfs(k+1,x,now,way*2);
//这一格已经被占住了，那么这一位不论贴什么都不行，直接把方案*2，状态不改
else {// 可以砍树，且一定砍
	now.c++;int fl=1;
	if(k<w){
		if(!(x.S&(1<<k)))dfs(k+2,x,now,way*2);// 下一个位置没有被占
		else fl=2;//不管贴什么都要往下砍，方案*2
	}
	now.S|=(1<<k-1);// 往下砍
	if(k<w)dfs(k+1,x,now,way*fl);//不是最后一个
	else dfs(k+1,x,now,way*2);// 最后一个
}