#P1293. 牧场的安排(cowfood)

    ID: 1293 传统题 文件IO:cowfood 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>动态规划状态压缩DPUSACO月赛

牧场的安排(cowfood)

题目描述

约翰新买了一块长方形的牧场.这块牧场被划分成M 列N 行(1 <= M <= 12; 1 <= N <= 12),每 一格都是一块正方形的土地.约翰打算在牧场上的某几格土地里种上美昧的草,供他的奶牛们享 用.遗憾的是,有些土地相当的贫瘠,不能用来放牧.并且,奶牛们喜欢独占一块草地的感觉,于是约翰不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边.当然,约翰还没有决 定在哪些土地上种草.

作为一个好奇的农场主,约翰想知道,如果不考虑草地的总块数,那么,一共有多少种种植 方案可供他选择.当然,把新的牧场荒废,不在任何土地上种草,也算一种方案.请你帮约翰算 一下这个总方案数.

输入说明

第1行:两个正整数M 和N .

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

输出说明

输出一个整数,即牧场分配总方案数除以100000000的余数.

输入样例

2 3
1 1 1
0 1 0

输出样例

9

样例说明

把各块土地编号:

1 2 3

0 4 0

只开辟一块草地的话,有4种方案.选1、2、3、4中的任一块;开辟两块草地的话,有3种方案.1、3,1、4以及3、4;选三块草地只有一种方案.1、3、4;再加把牧场荒废的那一种,总方案数为4 + 3 + 1 + 1 = 9种.

来源信息

Richard Ho, 2006