TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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