AngenommenM * N Gitter und Position von zwei Spielernp1 undp2auf dem Gitter. Es gibt n Bälle, die an verschiedenen Positionen auf dem Gitter platziert sind. Lassen Sie die Position dieser Bälle seinB(1), B(2), B(3) ..., B(n).

Wir müssen das @ berechnminumum manhattan distance erforderlich, um alle Bälle zu holen. Bälle sollten in aufsteigender Reihenfolge ausgewählt werden, d. H. WennB(i) wird vor @ gepicB(j) wenni < j.

Betrachten Sie den folgenden Beispielfall:
p1 = (1, 1) p2 = (3, 4) Betrachten wir die Position der Bälle alsB(1) = (1, 1), B(2) = (2, 1), B(3) = (3, 1), B(4) = (5, 5)
Ausgab wird sein5 weilp1 wählt zuerstB(1), B(2), B(3) undp1 wird wählenB(4)

Mein Ansat
Ich habe eingieri Ansat und berechneter Abstand vonp1 undp2 von einem bestimmten BallB(i) (abi = 1 to n) und fügte der Ausgabe das Minimum hinzu und aktualisierte die Position des Players entsprechend.
Aber dieser Ansatz schlägt für viele Testfälle fehl.

P.S: Diese Frage wurde in einem meiner letzten Interviews gestellt undO(n) Lösung für dieses Problem wird erwartet.

Edit: Weitere Testfälle können wie @ se
p1 = (1,1) p2 = (3,5)
B(1) = (3, 3), B(2) = (1, 1), B(3) = (4, 5), B(4) = (2, 1), B(5) = (4, 3).
In diesem Fallp1 wird wählenB(2), B(4) undp2 wird wählenB(1), B(3), B(5)
Ausgab wird 8 sein.

p1 = (1,1) p2 = (3,4)
B(1) = (2, 2), B(2) = (3, 2), B(3) = (4, 2), B(4) = (1, 1)
In diesem Fallp1 wird wählenB(4) undp2 wird wählenB(1), B(2), B(3)
Ausgab wird 5 sein.
Hinweis:Wenn der Spieler einen Ball auswählt, bewegt er sich zu diesem Punkt.

P.P.S. Nach Diskussion glaube ichkeine lineare Lösung existiert zu diesem Problem undO (n ^ 2) Lösung ist die beste verfügbare Lösung.