净水机器(Purifying Machine)

题目描述

本题对应 POJ 2724 / ICPC Latin America 2005：Purifying Machine。

奶酪工厂的净水机器需要对一批受到污染的 $N$ 位二进制编号水样进行净化。共有 $M$ 条污染记录，每条记录是一个长度为 $N$ 的字符串，由字符 0、1 和至多一个通配符 * 组成（其中 * 表示该位既包含 0 也包含 1 的两个水样编号）。

净水机器每次操作可以：

• 单独净化 $1$ 个水样编号；或者
• 同时净化恰好有 $1$ 位二进制位不同的 $2$ 个受污染水样编号（通过使用 * 通配符一次匹配它们）。

每个受污染的水样编号必须至少被净化一次，且不允许净化未受污染的水样编号。请你求出净化全部受污染水样所需的最少操作次数。

输入格式

输入包含多组测试数据。每组测试数据的第一行包含两个整数 $N, M$（$1 \le N \le 10$，$1 \le M \le 1000$）。

接下来 $M$ 行，每行一个长度为 $N$ 的字符串，仅含 0、1 和至多一个 *。

当 $N = 0$ 且 $M = 0$ 时表示输入结束。

输出格式

对于每组测试数据，输出一行一个整数，表示最少需要的净化操作次数。

样例输入 #1

3 3
01*
100
011
0 0

样例输出 #1

2

数据范围

对于 $100\%$ 的数据，$1 \le N \le 10$，$1 \le M \le 1000$，测试数据组数不超过 $20$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接