TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

95.6% (131/137)

Submission's AC Ratio

58.6% (311/531)

Tags

Description

在一個N x N的平面上 (1 <= N <= 500),有K塊隕石 (1 <= K <= 10,000),分別在一些格子中。卡恩想要用他的強者光束把所有隕石給清除,每一次使用強者光束都可以把某一整行或一整列的隕石給消滅。但由於卡恩對演算法的狂熱,他除了要清除所有隕石,還希望使用最少次的強者光束。
今給出所有隕石的位置,試問最少要使用幾次強者光束,才能把所有的隕石消滅?

(原文)
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 <= K <= 10,000), which are conveniently located at the lattice points of the grid.
Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot. This weapon is quite expensive, so she wishes to use it sparingly.
Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

Input Format

第一行有兩個整數N和K,分別代表平面的邊長(有幾個格子)以及有幾塊隕石。
接下來K行,每行有兩個數R和C,代表一塊隕石的位置(第幾列,第幾行)。

(原文)
* 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.

Output Format

請輸出一個數字,代表最少要使用幾次強者光束?

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

Sample Input 1

3 4
1 1
1 3
2 2
3 2

Sample Output 1

2

Hints

卡恩好威!

(Tmt補註:下次要改成球主啦= =+)

Problem Source

原TIOJ1089 / USACO Gold Demo, 2005 Nov。Translation/Problem Setter: kelvin。

Subtasks

No. Testdata Range Score
1 0 8
2 1 8
3 2 8
4 3 8
5 4 8
6 5 8
7 6 8
8 7 8
9 8 8
10 9 8
11 10 8
12 11 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
10 1000 65536 262144 11
11 1000 65536 262144 12