题目描述
约翰购买了由m × n （1≤m ，n ≤12）的方格组成的矩形牧场，想在一些方格上种玉米。遗憾的是，有些方格土壤贫瘠，无法种植。约翰在选择种植哪些方格时，会避免选择相邻的方格，没有两个选定的方格共享一条边。约翰考虑了所有可能的选择，他认为没有选择方格也是一种有效的选择！帮助他选择种植方格的方案数。
输入
第1行包含以两个空格分隔的整数m 和n 。后面有m 行，每行都包含n 个整数，表示一个方格是否肥沃（1表示肥沃，0表示贫瘠）。
输出
单行输出选择种植方格的方案数模100000000。
提示
按如下方式对肥沃的方格进行编号，仅在一个方格上种植有4种方案（1、2、3或4），在两个方格上种植有3种方案（13、14或34），在三个正方形上种植有1种方案（134），还有1种方案是所有方格都不种植。所以一共有4+3+1+1=9种方案。
1 2 3
4