我如何......解决这个问题？（旧的GOLD USACO问题） [英] How do I...solve this problem ?(old GOLD USACO problem)

问题描述

我们遇到了这个问题：

'Bessie希望通过一个N x N网格形状的危险小行星

场导航她的飞船（1 <= N <= 500）。网格

包含K个小行星（1 <= K <= 10,000），它们位于网格的格点处，非常方便。

。



幸运的是，Bessie拥有一种强大的武器，只需一次射击即可在网格的任何给定行或列中蒸发所有

小行星。

这种武器非常昂贵，所以她希望谨慎使用它。

鉴于所有小行星在现场的位置，找到

的最小数量Bessie需要开火以消灭所有的小行星。

我们输入两行：

*第1行：两个整数N和K，由一个空格分隔。



*行2..K + 1：每行包含两个以空格分隔的整数R和

C（1< = R，C< = N）分别表示

的行和列坐标为小行星。



并且要求打印所需的最小镜头！

起初看起来很容易...

你比较Y和X坐标，找到具有相同X或Y的小行星的最大数量，并在坐标或纵坐标处'火'有更多的小行星......并且循环直到没有人离开！

但是如果Xmax = Ymax怎么办？

我应该破坏我想要的任何东西或者我应该去哪里更深？

我真的很困惑

还有：你认为有一种比我更好的方法来解决这个问题吗？

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 ?

推荐答案

这是一个好的开始。每次消除一行时，它也可能已经消除了多列（反之亦然）。



每一轮Bessie用她的大炮清除一行或一列后，您需要重新计算行最大值和列最大值。



考虑一个小行星地图，其中第一行填充N小行星，第一列填充N小行星。



虽然最大行是N而最大列是N，但是这个字段可以两次清除。

That's a good start. Each time a row is eliminated, it may have also eliminated multiple columns (and vice versa).

After each round where Bessie clears a row or column with her cannon, you will need to recompute your row max and column max values.

Consider an asteroid map where the first row is filled with "N" asteroids and also the first column is filled with "N" asteroids.

Although the max row is N and the max column is N, this field can be cleared with two shots.

这篇关于我如何......解决这个问题？（旧的GOLD USACO问题）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！