No.3060 Erase Binary Matrix
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : 👑
tute7627
/ テスター :
👑
rin204
👑
SPD_9X2
タグ : / 解いたユーザー数 13
作問者 : 👑


問題文最終更新日: 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$ を空行列にできます。
- 操作 $3$ を $1$ 行目に行う
- 操作 $1$ を $1$ 行目に行う
- 操作 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。