問題一覧 > 通常問題

No.3060 Erase Binary Matrix

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : 👑 tute7627 / テスター : 👑 rin204 👑 SPD_9X2
5 ProblemId : 11516 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-03-12 02:46:18

問題文

$H$ 行 $W$ 列の行列 $A$ が与えられます。

はじめ、行列 $A$ の $i$ 行目 $j$ 列目の要素は $A_{i,j}$ です。ここで、 $A_{i,j}$ は 0 または 1 です。

あなたは行列 $A$ が空行列になるまで以下のいずれかの操作を任意の順番で任意の回数繰り返すことができます。

  • 操作 $1$: すべての値が同じであるような行を一つ選び、その行を削除する
  • 操作 $2$: すべての値が同じであるような列を一つ選び、その列を削除する
  • 操作 $3$: 行を一つ選び、削除する

行列 $A$ を空行列にするまでに行う操作 $3$ の回数としてあり得る最小値を求めてください。

入力

$H\ W$
$A_{1,1}A_{1,2}\dots A_{1,W}$
$A_{1,1}A_{1,2}\dots A_{2,W}$
$\vdots$
$A_{H,1}A_{H,2}\dots A_{H,W}$

  • $1 \le H,W \le 500$
  • $A_{i,j}$ は 0 または 1

出力

操作 $3$ の回数としてあり得る最小値を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
4 3
101
111
010
010
出力
1

以下の手順で行列 $A$ を空行列にできます。

  1. 操作 $3$ を $1$ 行目に行う
  2. 操作 $1$ を $1$ 行目に行う
  3. 操作 $2$ を各列に行う
101 -> 111 -> 010 -> 10 -> 0 -> (空)
111    010    010    10    0
010    010
010    
                

サンプル2
入力
4 4
1111
1000
1011
1010
出力
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。