問題一覧 > 通常問題

No.226 0-1 Puzzle

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 76
作問者 : drken1215
お気に入りにしたユーザー ProblemId : 600 / 自分の提出
問題文最終更新日: 2026-06-25 12:17:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 110 (順位表) の他の問題:

Problem Statement

There is a rectangle consisting of cells with height \(H\) and width \(W\), and each cell has one of '0', '1', or '?' written on it.
Now, for every cell with '?' written on it, we want to erase the '?' and write '0' or '1' so that the following condition is satisfied.
Write a program that finds the number of ways to do this, mod. 1000000007.

(Condition)
Every 2×2 square board taken out contains exactly two 0s and exactly two 1s.
More precisely, letting \(v(i, j)\) denote the value of the cell that is \(i\)-th from the top (1-index) and \(j\)-th from the left (1-index) of the board,
for any \(1 \leq i \leq H-1\), \(1 \leq j \leq W-1\), among the four values \(v(i, j), v(i, j+1), v(i+1, j), v(i+1, j+1)\),
exactly two are '0' and exactly two are '1'.

Input

\(H\) \(W\)
\(S_1\)
\(S_2\)
⋮
\(S_H\)

The first line contains \(H\) and \(W\), separated by a space.
Each of the following \(H\) lines contains a string \(S_i\) of length \(W\) representing how the \(i\)-th row of cells is filled.

\(2 \leq H \leq 100\)
\(2 \leq W \leq 100\)
\(S_i\) is a string consisting only of '0', '1', and '?'

Output

Output the number of ways mod. 1000000007.
Print a newline after the output.

Sample

Sample 1
Input
2 4
?11?
???0
Output
2

There are the following 2 ways.
0111  1111
1000  0000

Sample 2
Input
3 3
1??
??0
???
Output
3

There are the following 3 ways.
101  101  111
010  010  000
101  010  111

Sample 3
Input
50 50
1????????????????????????????????????????????????0
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
??????????????????????????????????????????????????
0????????????????????????????????????????????????1
Output
949480668

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