Maximale Summe von k verbundenen Elementen einer Matrix
Gegeben ein Gitter mit positiven ganzzahligen Werten und einer Ganzzahl K . Was ist die maximale Summe der K verbundenen Elemente?
Hier ist ein Beispiel für eine 5x5 Matrix mit einem K Wert von 6.
Jemand kann mir helfen, dieses Problem zu identifizieren? Wie kann ich beginnen, es zu lösen? Der einzige Weg, den ich kenne, ist eine Tiefensuche nach jeder Zelle dieser Matrix. Aber ich denke, das ist nicht der beste Ansatz.
Wiederholte Zellen sind nicht erlaubt.
Verbunden bedeutet hier nur, dass eine Zelle horizontal oder vertikal an die andere angrenzt
1 Antwort
Ich nehme an, du könntest herumschlendern, während du gehst. Ich habe spiegelbildliche Bitsets verwendet, um die Memo-Pfade so darzustellen, dass sie aus jeder beliebigen Richtung sofort erkennbar sind. Hier ist eine Version in Python (die Hash-Länge enthält Zählungen für Pfade von Größe eins bis sechs):
%Vor%Ausgabe:
%Vor% UPDATE: Diese Frage ist ähnlich wie diese, Was ist der schnellste Weg, um die größte Summe von M benachbarten Elementen in einer Matrix zu finden , und ich erkannte, dass eine Überarbeitung in meinem Vorschlag erforderlich ist, um Formationen aus mittleren Abschnitten von die Formen. Hier ist mein überarbeiteter Code, der Sets zum Hashing der Shapes verwendet. Es scheint mir, dass ein DFS die Stackgröße in der Größenordnung von O(m) behalten sollte (obwohl der Suchraum immer noch riesig ist).
Ausgabe:
%Vor%