问题2166--小行星2166: 小行星
时间限制: 1 Sec 内存限制: 128 MB
提交: 2 解决: 2
[提交] [状态] [讨论版] [命题人:]题目描述
贝茜想在N x N网格（1 <= N < = 500）形状的危险小行星场中导航她的宇宙飞船。网格包含 K 颗小行星（1 <= K <= 10，000），它们位于网格的晶格点，非常方便。
幸运的是，贝茜拥有强大的武器，可以一枪将网格中任何给定行或列中的所有小行星蒸发。这种武器相当昂贵，所以她希望谨慎使用它。考虑到该领域所有小行星的位置，找到贝西需要发射的最小射击次数，以消除所有小行星。
输入
* 第 1 行：两个整数 N 和 K，由单个空格分隔。
* 2..K+1线：每条线包含两个以空格分隔的整数R和C（1 <= R，C <= N），分别表示小行星的行坐标和列坐标。
输出
* 第 1 行：表示 Bessie 必须拍摄的最少次数的整数。
样例输入
3 4
1 1
1 3
2 2
3 2
样例输出
2
提示
输入详细信息：
下图表示数据，其中"X"是小行星，"."是空白空间：
X.X
.X.
.X.
输出详细信息：
Bessie可能会发射第1行以摧毁（1，1）和（1，3）处的小行星，然后她可能会向下发射列2以摧毁（2，2）和（3，2）处的小行星。
来源/分类
[提交] [状态]