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; }