TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1902
  • Problem
  • P1902【S2状态压缩】玉米地
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    2 3
    1 1 1
    0 1 0

    Sample Output

    9

    Hint

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


    Source  UASCO 2006 GOLD