we have this problem :
'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.'
we are given an input of two lines :
* 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.
and the request is to print the minimum shots needed!
at first it seemed very easy...
you compare the Y and X coordinates,find the maximum number of asteroids having the same X or Y and 'fire' at the coordinate or ordinate that has the more asteroids...and loop till there's noone left !
but what if Xmax=Ymax ?
should I 'destroy' whatever I want or should I go deeper ?
I am really confused
also :do you think there is a better way than mine to solve this problem ?
Submit an article or tip