0

私は 2D 配列を持っています。この配列には、X などの n 個の同一の要素がランダムな位置に配置されています。1 つのステップで行全体または列全体を削除することによって、そのような X をすべて削除できるという条件を考えると、そのような X をすべて削除するために必要な最小ステップ数を計算する必要があります。例として、2x2 配列の場合、位置 (0,0)、(1,0)、および (0,1) の X を 2 ステップで削除できます [1 for (0,0), (0,1) and (1,0) の場合は 1]

私自身がアプローチを思いつきました.x座標とy座標を2つの別々の配列に保存し、両方の異なる座標を数えています。両方を比較すると、最小の別個の要素を持つ方が答えになります。つまり、必要なステップの最小数です。

私はこれをさまざまな入力に対してチェックしましたが、私の答えは毎回正しいようです。しかし、私のインストラクターは、理由を説明しませんが、この答えは間違っていると言います。彼が言うのは、特定のテスト ケースで失敗したということだけですが、それについては言及しません。

したがって、私は助けを求めています。このアプローチで失敗を見つけることができたら、教えてください。感謝します。ありがとう。

4

1 に答える 1

2

私があなたのことを理解していると仮定して

x 座標と y 座標を 2 つの別々の配列に格納し、両方の個別の座標をカウントしています。両方を比較すると、最小の別個の要素を持つ方が答えになります。つまり、必要なステップの最小数です。

アルゴリズムが正しい場合、1 つの単純な反例は次のとおりです。

  [[1, 1, 1],
   [1, 0, 0],
   [1, 0, 0]]

a が配置されている場所には、3 つの異なる x 座標と 3 つの異なる y 座標があり1ますが、明らかに 2 つの削除操作しか必要ありません。

于 2013-10-05T15:17:08.433 に答える