题目描述

农场主John新买了一块长方形的新牧场,这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12),每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。

遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是John不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。

John想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)

输入输出格式

输入格式:

第一行:两个整数M和N,用空格隔开。

第2到第M+1行:每行包含N个用空格隔开的整数,描述了每块土地的状态。第i+1行描述了第i行的土地,所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块土地不适合种草。

输出格式:

一个整数,即牧场分配总方案数除以100,000,000的余数。

输入输出样例

输入样例#1:
2 3
1 1 1
0 1 0
输出样例#1:
9


看数据识算法…状压直接搞上
先YY出一个状态转移方程
考虑从i:1~m
如果当前state不与原先state冲突,则
f[i][state]+=f[i-1][j]
具体要枚举当前行状态和上一行状态

对于合法状态…定义一个F[13]数组
F[i]表示这一行草地的情况
比如样例,F[1]=111
用枚举的状态j j&F[i]==j判断合法

然后处理出来一个now数组
表示这个状态的奶牛不冲突

代码很短

 


1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
你猜猜 Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
你猜猜
游客
你猜猜

orzzzzz