一个棋盘上有几个能藏着拦截器的鱼钩？

Question

您将得到一个m*n棋盘(其中m≤n≤50 )和x个被阻塞的单元格。我们知道被阻断的细胞在哪里，我们知道它们的确切位置。

你的工作是提供最多的鲁克斯数量，你可以放在棋盘上，这样没有2个罗克斯互相攻击。

任何语言中的任何伪代码，甚至代码都是有帮助的。

输入输出样本：

在3*3棋盘中，

X=3

阻断细胞：(0，0)，(0，1)，(0，2)

答案=2

Answer 1

1. 在每列的最后一行之后添加一个阻止程序。
2. 按照列第一列、第二行对阻滞剂进行排序。
3. 在每列中添加一个数组，其中包含第一个阻滞剂的索引。对于每一行，
4. 都要查找未使用的列，并在每个空闲范围内找到最近的阻滞剂(如果有多个候选项，则可以使用任何选项)。used.
5. Advance
6. Place在那里建立并标记为的所有列，在这些列中遇到块，标记列为usable.

​

总之，算法应该在O(n *m+x* log(x))中运行.