本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden ☆ before use]

1154. 猛兽军团2


Description

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

Input

第一行:两个整数M(0≤M≤12) 和N(1≤N≤12)
接下去M行:每行包括N个用空格隔开的整数,0代表不可放置,1代表可以放置。

Output

放置方案个数(个数可能较大,取100000000的余数)

Samples

Input Copy
2 3
1 1 1
0 1 0
Output
9

Source

算法宝典2 状态压缩动态规划
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 5 / 9
Tags:
Contests involved

1019. 算法宝典2 DP 状态压缩
My history solutions

You didn't submit any solution!
Submit your solution

Login Register