[Usaco2007 Demo]Asteroids

题目描述

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= n="" <="500)." the="" grid="" contains="" k="" asteroids="" (1="" which="" are="" conveniently="" located="" at="" lattice="" points="" of="" grid.="" fortunately,="" bessie="" has="" a="" powerful="" weapon="" that="" can="" vaporize="" all="" in="" any="" given="" row="" or="" column="" with="" single="" shot.="" this="" is="" quite="" expensive,="" so="" she="" wishes="" to="" use="" it="" sparingly.="" location="" field,="" find="" minimum="" number="" shots="" needs="" fire="" eliminate="" asteroids.="" p="">

---

输入格式

* Line 1: Two integers N and K, separated by a single space. * Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= r,="" c="" <="N)" denoting="" the="" row="" and="" column="" coordinates="" of="" an="" asteroid,="" respectively.="" p="">

---

输出格式

* Line 1: The integer representing the minimum number of times Bessie must shoot.

---

样例输入

3 4
1 1
1 3
2 2
3 2

INPUT DETAILS:

The following diagram represents the data, where "X" is an
asteroid and "." is empty space:
X.X
.X.
.X.

---

样例输出

2

OUTPUT DETAILS:

Bessie may fire across row 1 to destroy the asteroids at (1,1) and
(1,3), and then she may fire down column 2 to destroy the asteroids
at (2,2) and (3,2).

---

提示

没有写明提示

---

题目来源

Gold