No.226 0-1 Puzzle
タグ : / 解いたユーザー数 76
作問者 :
drken1215
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
3There 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もしくは右上の雲マークをクリックしてアカウントを作成してください。