TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1902
  • 题目
  • P1902【S2状态压缩】玉米地
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Farmer John买了一片土地,可以表示为一片由方块组成的网格,长度为M,宽度为N(1 <= M, N <= 12)。现在FJ要在地里种上一些玉米让他的奶牛们直接在地里食用。FJ知道他的这片土地有些地方很贫瘠,没有办法种玉米;并且奶牛们不喜欢挨在一起吃玉米,所以不能在相邻的两块地上种玉米。请帮助FJ计算一下所有可能的种玉米的方案数。注意,结果输出对于100,000,000的余数,一棵玉米也不中也算是一种方案。

    输入格式

    第一行 两个整数M和N
    接下来是一个M*N的矩阵,1表示该方块可以种玉米,0表示不行

    输出格式

    一个整数,表示对应的结果

    样例输入

    2 3
    1 1 1
    0 1 0

    样例输出

    9

    提示

    把每块能中玉米的地编上号:
    1 2 3
    0 4 0
    只种一块地,方案有(1, 2, 3, 4);种两块地方案有 (13, 14, 34);种三块地 (134),
    一块也不种也算一种方案,总共4+3+1+1=9


    来源  UASCO 2006 GOLD