P2446 - 放牛

内存限制：256 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：3 通过：3

农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以放牧的（用1标记），农夫可以在这些格子里放牛，其他格子则不能放牛（用0标记），并且要求不可以使相邻格子都有牛，否则牛会打架。现在输入数据给出这块地的大小及可否放牧的情况，求该农夫有多少种放牧方案可以选择（注意：任何格子都不放也是一种选择，不要忘记考虑！）

第一行是M和N，1<=M,N<=12。后面有M行，描述方格情况,1表示肥沃，可以放牛，0表示贫瘠。

方案数，用10⁹取模。

输入：

2 3
1 1 1
0 1 0

输出：

分别是{},{1},{2},{3},{4},{1},{1,3},{1,4},{3,4},{1,3,4}

2 3
1 1 1
0 1 0

状态压缩

2446: 放牛

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签