読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

UnKoder #02 Binary Matrix

気づかなかった…

問題:Programming Problems and Competitions :: HackerRank

解法:例えばひとつの列で0のビンゴがあったとすると,もう1が行でビンゴを作ることはありえなくなる(下図(0列に0のビンゴができている)のようになるので)。
0111
0111  <-もういくら1をつくっても0の壁ができているのでビンゴはできない
0111

なので,ビンゴの数が最大になった時のシチュエーションとして考えられるのは以下の4通りのみ。
・すべてのビンゴが0で構成される
・すべてのビンゴが1で構成される
・行のみでビンゴが作られる
・列のみでビンゴが作られる
これらをすべて調べれば良い。
以下ソースコード

const int MAXN = 64;
string s[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> s[i];
    int ans = 0;
    {
        int tmp = 0;
        for (int i = 0; i < N; i++) {
            int j;
            for (j = 0; j < M; j++) {
                if (s[i][j] == '1') break;
            }
            if (j == M) tmp++;
        }
        for (int i = 0; i < M; i++) {
            int j;
            for (j = 0; j < N; j++) {
                if (s[j][i] == '1') break;
            }
            if (j == N) tmp++;
        }
        ans = max(ans, tmp);
    }
    {
        int tmp = 0;
        for (int i = 0; i < N; i++) {
            int j;
            for (j = 0; j < M; j++) {
                if (s[i][j] == '0') break;
            }
            if (j == M) tmp++;
        }
        for (int i = 0; i < M; i++) {
            int j;
            for (j = 0; j < N; j++) {
                if (s[j][i] == '0') break;
            }
            if (j == N) tmp++;
        }
        ans = max(ans, tmp);
    }
    {
        int tmp = 0;
        for (int i = 0; i < N; i++) {
            int cnt[3];
            cnt[0] = cnt[1] = cnt[2] = 0;
            for (int j = 0; j < M; j++) {
                if (s[i][j] == '0') cnt[0]++;
                if (s[i][j] == '1') cnt[1]++;
                if (s[i][j] == '?') cnt[2]++;
            }
            if (cnt[0] == 0 || cnt[1] == 0) tmp++;
        }
        ans = max(ans, tmp);
    }
    {
        int tmp = 0;
        for (int i = 0; i < M; i++) {
            int cnt[3];
            cnt[0] = cnt[1] = cnt[2] = 0;
            for (int j = 0; j < N; j++) {
                if (s[j][i] == '0') cnt[0]++;
                if (s[j][i] == '1') cnt[1]++;
                if (s[j][i] == '?') cnt[2]++;
            }
            if (cnt[0] == 0 || cnt[1] == 0) tmp++;
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}