猛兽军团2

成绩 100 开启时间 2016年05月30日 星期一 21:45
折扣 0.8 折扣时间 2016年05月30日 星期一 21:45
允许迟交 是 关闭时间 2016年05月30日 星期一 21:45
输入文件 embattle2.in 输出文件 embattle2.out

【题目描述】猛兽军团2（embattle2.cpp/c/pas )PKU 3254

　　事实证明，理想和现实总是存在差距，修罗王到了战场才发现，猛兽军团只能放置在一个M×N的矩阵，而且部分方格由于地形限制无法放置猛兽，请问猛兽与猛兽若不能相邻，有多少种放置方案（注：经过修罗王的三观教育，猛兽之间的关系略显缓和，但仍不能彼此相邻）？

　　【输入格式】

　　第一行：两个整数M(0≤M≤12) 和N(1≤N≤12)

　　接下去M行：每行包括N个用空格隔开的整数，0代表不可放置，1代表可以放置。

　　【输出格式】

　　放置方案个数（个数可能较大，取100000000的余数）

　　【输入样例】

　　2 3

　　1 1 1

　　0 1 0

  　【输出样例】

　　　9