4

ウェブサイトでこのプログラミング パズルを見て、解こうとしました。

問題

特定のドットがランダムに分散された N x N グリッドが与えられます。次の許可されたアクションを使用して、ドットを削除する必要があります。

  • 1回のショットで連続してすべてのドットを削除できます

  • または、1 回のショットで列内のすべてのドットを削除できます。

すべてのドットを削除するために必要な最小ショット数を見つける必要があります。

例

次のグリッドでは、ドットを削除するために、水平方向に 1 つ、垂直方向に 2 つの 3 つのショットが必要です。

ここに画像の説明を入力

行と列をドットでカウントするというアプローチを試しましたが、最小のものが答えになります。しかし、上記の例のような特定のケースでは失敗します。それを行う方法は何ですか、またはこの問題を解決するために参照できるそれに類似した状況はありますか?

編集

与えられた制約は

1 <= N <= 1000
0 <= x,y <= 10^9
Time Limit: 2 sec

ここで、n はグリッドの次元 (つまり nxn) で、x、y は座標です

4

3 に答える 3

0

徹底的なアルゴリズムを試してみます。正しく行えば、思ったほど悪くはありません。

最悪の場合、N 回のショットが必要になることは既にご存じでしょう (すべての行またはすべての列で撮影すれば、確実に機能します)。

したがって、最悪のケースを改善するには、可能な列ショット + 行ショットのすべての順列を試す必要があるだけです。ここで、ショットの総数は N 未満です。たとえば、N=4 の場合、自明でない解は <= でなければなりません。 3、すべての (列、行) ショットを試してください。

(0,3)
(1,2)
(2,1)
(3,0)

ショットを撮りたい任意の軸 (列または行) について、(s choose N)可能性があります。したがって、大きな N の可能性の総数は、(N/2) choose Nとにかく N < 30 ではそれほど悪くないようなものです。

より良いヒューリスティックがあると確信しており、より悪い場合のアルゴリズムもあるかもしれません。

于 2013-10-09T06:32:47.257 に答える