問題一覧 > 通常問題

No.226 0-1パズル

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : drken1215
7 ProblemId : 600 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:19

問題文

縦H, 横Wのマスからなる長方形があり、各マスには'0'か'1'か'?'のいずれかが書かれている。
今、'?'の書かれている全てのマスに対し、以下の条件を満たすように、'?'を消して'0'か'1'を書き込みたい。
そのような方法のパターン数を mod. 1000000007 で求めるプログラムを書いて下さい。

(条件)
どの2×2の正方形ボードを取り出しても、0が丁度2個、1が丁度2個含まれている。
より正確には、ボードの上からi番目 (1-index)、左からj番目 (1-index) のマスの値をv(i,j)と表したとき、
任意の 1≤i≤H−1, 1≤j≤W−1 に対し、4個の値 v(i,j),v(i,j+1),v(i+1,j),v(i+1,j+1) のうち、
丁度2個が'0'で、丁度2個が'1'となっている。

入力

H W
S1
S2
⋮
SH

一行目にH, Wがスペース区切りで与えられます。
続くH行には、マスのi行目の塗られかたを表す長さWの文字列Siが与えられます。

2≤H≤100
2≤W≤100
Siは、'0'と'1'と'?'のみから構成される文字列である

出力

パターン数 mod. 1000000007 を出力して下さい。
出力した後には改行して下さい。

サンプル

サンプル1
入力
2 4
?11?
???0
出力
2

以下の2通りがあります。
0111　　1111
1000　　0000

サンプル2
入力
3 3
1??
??0
???
出力
3

以下の3通りがあります。
101　　101　　111
010　　010　　000
101　　010　　111

サンプル3
入力
50 50
1????????????????????????????????????????????????0
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
0????????????????????????????????????????????????1
出力
949480668

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。