yukicoder No.226 0-1パズル

いやぁこれ結構実装大変だと思うんですけど…
なんか一発ACしてる人多いですねぇ。

問題

No.226 0-1パズル - yukicoder

解法

基本的な方針は,「上の行が決まると下の行も決まるんじゃね？」ということです。

この予想はある程度正しくて,上の行に少なくともひとつ0か1が連続している部分があると,下の行は完全に一意に決定します(上の行をbit反転したものが下の行)。

ただ,上の行が01010101...のように１つおきにバラバラだと下の行は101010101...のようにbit反転するものと,01010101...のように上と同じbit行にするものの2通りがあります。

実装の方針は,

すべての行を0101010のように1つおきにバラバラにするものと,1行目を適当に決めたらそれより下の行が決定されるもの,に場合分けする,という方針でやりました(若干場合がかぶるのでなんとかする)。

1つおきにバラバラの場合は1行ずつ見ていって0からスタートするものと1からスタートするものが存在するかを見ていきます。

1行目を決めて残り全部を決める場合は,すべて反転していないと行けないので例えば下のように0,1が決まっていたとすると,
?11?
???0
次のように0,1が決定します。
?111
?000
1行目の残りの?は好きに決めて良いので2とおりです。

後は気合でACしました。

const int MAX = 111;
const ll MOD = 1e9+7;
int H, W;
string board[MAX];

ll calc() {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (board[i][j] != '?') {
                for (int k = 0; k < H; k++) {
                    const int diff = abs(i-k) % 2;
                    int should = board[i][j] - '0';
                    if (diff == 1) should ^= 1;
                    char c = (char)('0'+should);
                    if (board[k][j] != '?' && board[k][j] != c) {
                        return 0;
                    }
                    board[k][j] = c;
                }
            }
        }
    }
    //for (int i = 0; i < H; i++) cout << board[i] << endl;
    ll ans = 1;
    for (int i = 0; i < W; i++) {
        if (board[0][i] == '?') (ans *= 2) %= MOD;
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    for (int i = 0; i < H; i++) cin >> board[i];
    ll ans = 1;
    for (int i = 0; i < H; i++) {
        // 101010的something
        int ok = 0; // 最初1, 最初0 でないと11
        for (int j = 0; j < W; j++) {
            if (board[i][j] == '0') {
                if (j%2) ok |= 2;
                else ok |= 1;
            }
            if (board[i][j] == '1') {
                if (j%2) ok |= 1;
                else ok |= 2;
            }
        }
        int tmp = 2-__builtin_popcount(ok);
        ans *= tmp;
        ans %= MOD;
    }
    ll tmp = calc();
    ans += tmp;
    ll cnt = 0;
    if (tmp != 0) {
        int ok = 0; // 最初1, 最初0 でないと11
        for (int i = 0; i < W; i++) {
            if (board[0][i] == '0') {
                if (i%2) ok |= 2;
                else ok |= 1;
            }
            if (board[0][i] == '1') {
                if (i%2) ok |= 1;
                else ok |= 2;
            }
            cnt = 2-__builtin_popcount(ok);
        }
    }
    cout << (ans-cnt) % MOD << endl;
    return 0;
}