結果

問題 No.226 0-1パズル
ユーザー nemunemu nemunemu
提出日時 2023-10-14 16:43:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,309 bytes
コンパイル時間 817 ms
コンパイル使用メモリ 75,544 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2024-09-16 11:02:06
合計ジャッジ時間 7,339 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:36:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   36 |                 for (auto [row, col]: qidxlst) {
      |                           ^
main.cpp:42:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   42 |                 for (auto [row, col]: qidxlst) {
      |                           ^

ソースコード

diff # 

// No.226 0-1パズル
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MOD = 1'000'000'007;

int main() {
    int H, W;
    cin >> H >> W;

    vector<string> S(H);
    for (int i = 0; i < H; ++i) cin >> S[i];

    int res = 0;
    for (int bit = 0; bit < (1 << W); ++bit) {
        vector<string> tmp = S;
        int num = 1;

        auto check = [&](int i, int j) {
            int cnt0 = 0, cnt1 = 0, cntq = 0;
            vector<pair<int, int>> qidxlst;
            for (int row = i; row <= i + 1; ++row) {
                for (int col = j; col <= j + 1; ++col) {
                    if (tmp[row][col] - '0' == 0) ++cnt0;
                    if (tmp[row][col] - '0' == 1) ++cnt1;
                    if (tmp[row][col] == '?') {
                        ++cntq;
                        qidxlst.push_back(make_pair(row, col));
                    }
                }
            }
            if (cntq > max(cnt0, cnt1)) return true;
            if (cnt0 < cnt1) {
                cnt0 += cntq;
                for (auto [row, col]: qidxlst) {
                    tmp[row][col] = '0';
                }
            }
            if (cnt1 < cnt0) {
                cnt1 += cntq;
                for (auto [row, col]: qidxlst) {
                    tmp[row][col] = '1';
                }
            }
            return cnt0 == cnt1;
        };

        bool flag = false;
        for (int j = 0; j < W; ++j) {
            if (tmp[0][j] == '?') {
                tmp[0][j] = ((bit >> (W - j - 1)) & 1) + '0';
            } else {
                if (((bit >> (W - j - 1)) & 1) != (tmp[0][j] - '0')) {
                    flag = true;
                    break;
                }
            }
        }
        if (flag) continue;
        
        for (int i = 0; i < H - 1; ++i) {
            for (int j = 0; j < W - 1; ++j) {
                if (!check(i, j)) {
                    flag = true; 
                    break;
                }
            }
            if (flag) break;
            bool flag2 = true;
            for (int j = 0; j < W; ++j) {
                if (tmp[i + 1][j] != '?') flag2 = false;
            }
            if (flag2) num *= 2;

        }
        if (flag) continue;
        res = (res + num) % MOD;
    }

    cout << res << endl;
}
0