AT_abc358_c [ABC358C] Popcorn

题目描述

AtCoder Land 有 $1$ 到 $N$ 编号的 $N$ 个爆米花售卖点。爆米花有 $M$ 种口味，分别为口味 $1,2,\dots,M$，但并不是每个售卖点都出售所有口味的爆米花。

高桥君获得了每个售卖点出售哪些口味爆米花的信息。这些信息由 $N$ 个长度为 $M$ 的字符串 $S_1,S_2,\dots,S_N$ 表示，如果 $S_i$ 的第 $j$ 个字符是 o，则表示第 $i$ 个售卖点出售第 $j$ 种口味的爆米花，如果是 x，则表示不出售。每个售卖点至少出售 $1$ 种口味的爆米花，每种口味的爆米花至少有 $1$ 个售卖点出售。

高桥君想要吃到所有口味的爆米花，但他不想多次移动。请你求出，为了买到所有口味的爆米花，他最少需要访问多少个售卖点。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出高桥君为了买到所有口味的爆米花，最少需要访问的售卖点数量。

输入输出样例 #1

输入 #1

3 5
oooxx
xooox
xxooo

输出 #1

2

输入输出样例 #2

输入 #2

3 2
oo
ox
xo

输出 #2

1

输入输出样例 #3

输入 #3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

输出 #3

3

说明/提示

限制条件

• $N,M$ 为整数
• $1 \leq N, M \leq 10$
• $S_i$ 是只包含 o 和 x 的长度为 $M$ 的字符串
• 对于所有 $i\ (1 \leq i \leq N)$，$S_i$ 中至少有一个 o
• 对于所有 $j\ (1 \leq j \leq M)$，存在至少一个 $i$ 使得 $S_i$ 的第 $j$ 个字符为 o

样例解释 1

访问第 $1$ 个和第 $3$ 个售卖点即可买到所有口味的爆米花。无法在一个售卖点买到所有口味，所以答案是 $2$。

由 ChatGPT 4.1 翻译