← 返回题目

题库练习奶牛的食物

← 上一题下一题 →

A71201 | $奶牛的食物$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

奶牛们的牧草快要吃完了！FJ 听了贝茜的抱怨后，买了一块 M \times N 的牧场，牧场可以被分成 M \times N 个格子，有的格子很肥沃，适合放牧。而有的很贫瘠，不适合放牧。 奶牛们的要求很苛刻，每只奶牛必须独占一个格子，并且任意两个奶牛的格子不能相邻（不能有公共的边）。 FJ 要选出一些格子来放牧，他想知道，有多少种方案？

输入格式

第一行两个数 M，N。 接下来 M 行，每行 N 个数，每个数均为 0 或 1，0 表示不适合放牧，1 表示适合放牧。 对于 100\% 的数据，N \le 12 ， M \le 12。 请注意：FJ 可以直接荒废新买的牧场，即不在任意一个格子放牧，这也算一种方案。

输出格式

一个数，表示方案数，答案 \mod 100000000 输出。

输入输出样例

输入 #1

2 3
1 1 1
0 1 0

输出 #1

C++ 编辑器

输入

输出