No.1908 Assault for Keys
タグ : / 解いたユーザー数 162
作問者 :
chineristAC
/ テスター :
tokusakurai
Kanten4205
問題文
chinerist 君はインデント幅を1にしてコーディングしていた罪で yuki 刑務所に投獄されてしまいました。
yuki 刑務所には $N$ 人の看守 $i\ (1\le i \le N)$ がいて、各看守は $M$ 種類の鍵 $j\ (1\le j \le M)$ のうちいくつかを所持しています。
看守 $i$ が各鍵を所持しているかについては o,x のみからなる長さ $M$ の文字列 $S_i=S_{i1}S_{i2}\dots S_{iM}$ で表され、 $S_{ij}=$o のとき看守 $i$ が鍵 $j$ を所持していることを、$S_{ij}=$x のとき看守 $i$ が鍵 $j$ を所持していないことを表します。
各鍵 $j\ (1\le j \le M)$ は $1$ 人以上の看守が所持しています。
yuki 刑務所から脱獄するには $M$ 種類の鍵がそれぞれ $1$ つ以上必要です。 chinerist 君は何人かの看守を襲って、それぞれが所持している鍵をすべて強奪することで鍵を集めることにしました。
以下の条件を満たす最小の整数 $K$ を求めてください。
条件- $N$ 人の看守のうちどの $K$ 人を襲っても、$M$ 種類の鍵をそれぞれ $1$ つ以上手に入れることができる
入力
$N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$
- $1 \le N \le 1000$
- $1 \le M \le 1000$
- $S_i$ は
o、xのみからなる長さ $M$ の文字列 - 各 $j\ (1\le j \le M)$ に対し、 $S_{ij}=$
oを満たす $i$ が1つ以上存在する
出力
答えを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 3 oxo xoo oox
出力
2
看守 $1$ だけ襲うと鍵 $2$ が集められません。
看守 $1,\ 2$ を襲うと $3$ 種類の鍵はすべて集まります。
看守を $2$ 人襲う方法として他に看守 $2,\ 3$ を襲う、看守 $1,\ 3$ を襲う、の $2$ 通りありますが、いずれの方法でも $3$ 種類の鍵はすべて集まります。
よって条件を満たす最小の $K$ は $2$ です。
サンプル2
入力
10 15 ooxxxxooooxoxox ooxxxooxooxxxxx ooooooxooooxxxx oxxoxooxoxoooxx oxooooxoooooxoo ooooxoxooooxxox oxooxoxoooxxxxx ooxoxoxoooooxoo oooxoooxooxooxo oxoxxoxooooxoxx
出力
8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。