问题1462--玉米田1462: 玉米田
时间限制: 1 Sec 内存限制: 128 MB
提交: 8 解决: 2
[提交] [状态] [讨论版] [命题人:]题目描述
农场主约翰购买了一个郁郁葱葱的新矩形牧场，由m×n（1≤m≤12；1≤n≤12）个方形地块组成。他想在一些广场上为奶牛种些好吃的玉米。遗憾的是，有些广场是不孕的，不能种植。Canny FJ知道奶牛不喜欢互相靠近吃东西，所以在选择种植哪一个方块时，他避免选择相邻的方块；没有两个选中的方块共用一条边。他还没有最终决定种植哪种方块。作为一个非常开明的人，农夫约翰想考虑所有可能的选择，如何选择广场种植。他是如此的开明，他认为选择没有广场是一个有效的选择！请帮助农夫约翰确定他可以选择种植方块的方法的数量。
输入
第1行：两个空格分隔的整数：m和n
第2.m+1行：第i+1行描述牧场的第一行，用N个空格分隔的整数表示一个正方形是否可育（1表示可育，0表示不可育）
输出
样例输入
2 3
1 1 1
0 1 0
样例输出
9
提示
对方块编号如下：
1 2 3 4
只有四种方法可以在一个方块上种植（1、2、3或4），三种方法可以在两个方块上种植（13、14或34），一种方法可以在三个方块上种植（134），一种方法可以在没有方块的地方种植。4＋3＋1＋1＝9。
来源 POJ 3254
来源/分类
[提交] [状态]