C++: Anzahl der Züge ermitteln, um Markierungen auf einem Raster zu platzieren [geschlossen] ⇐ C++

[Guest]

Mir wurde ein C++-Test unterzogen, bei dem ich die Anzahl der Züge ermitteln musste, die erforderlich sind, um einen Stein auf jedem Quadrat eines Gitters zu platzieren. Ich habe eine Lösung gefunden, die jedoch nur in 40 % der Fälle funktionierte. Bitte helfen Sie mir, eine Lösung zu finden. Nachfolgend finden Sie die Aufgabe und meine Lösung.
Aufgabe
Sie erhalten ein 3 x 3-Raster, das genau neun enthält Steine ​​in seinen Zellen. Eine Zelle kann eine beliebige Anzahl von Steinen enthalten.
Bei jedem Zug können Sie einen Stein von einer Zelle in eine andere verschieben, wenn die beiden Zellen eine gemeinsame Seite haben.
Das Gitter wird durch eine 3 x 3-Matrix aus ganzen Zahlen A beschrieben. Die Zeilen sind von 0 bis 2 von oben nach unten nummeriert. Die Spalten sind von links nach rechts von 0 bis 2 nummeriert. A[K][J] stellt die Anzahl der Steine ​​in der Zelle dar, die sich am Schnittpunkt der K-ten Zeile und der J-ten Spalte befindet.
Schreiben Sie eine Funktion:

Code: Select all

 int solution(vector &A)

dass bei gegebener Matrix A die minimale Anzahl an Zügen zurückgegeben wird, die erforderlich sind, um einen Stein in jeder Zelle zu platzieren.
Beispiele:

• Gegeben A =[[1, 0, 1], [1, 3, 0], [2, 0, 1 ]], die Funktion sollte 3 zurückgeben. Wir können einen Stein von (1, 1) nach (0, 1), von (1, 1) nach (1, 2) und von (2, 0) nach (2, 1).

• Gegeben A = [[2, 0, 2], [1, 0, 0], [2, 1, 1]], die Funktion sollte 4 zurückgeben.

• Gegeben A = [ [0, 6, 0], [2, 0, 0], [0, 1, 0]], die Funktion sollte 9 zurückgeben.

Lösung
Schreiben Sie einen effizienten Algorithmus für die folgenden Annahmen:

• A hat 3 Zeilen und 3 Spalten;
• jedes Element der Matrix A ist eine Ganzzahl im Bereich [0, 9];
  < li>A enthält genau 9 Steine.

Das Folgende ist meine Lösung, die in 60 % der Fälle, in denen ich sie getestet habe, fehlgeschlagen ist.

Code: Select all

#include 
#include 
#include 

using namespace std;

int solution(vector &A) {
struct Cell {
int index, excess;
};

vector excess_cells, deficit_cells;
int moves = 0;

// Flatten 3x3 grid into a 1D array and track excess/deficit positions
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
int index = i * 3 + j;  // Convert 2D index to 1D
int excess = A[i][j] - 1;

if (excess > 0) {
excess_cells.push_back({index, excess});
} else if (excess < 0) {
deficit_cells.push_back({index, -excess});
}
}
}

// Two-pointer approach to optimally pair excess with deficit
size_t i = 0, j = 0;
while (i < excess_cells.size() && j < deficit_cells.size()) {
int transfer = min(excess_cells[i].excess, deficit_cells[j].excess);

// Calculate Manhattan distance for movement
int row1 = excess_cells[i].index / 3, col1 = excess_cells[i].index % 3;
int row2 = deficit_cells[j].index / 3, col2 = deficit_cells[j].index % 3;
moves += transfer * (abs(row1 - row2) + abs(col1 - col2));

// Update remaining excess/deficit
excess_cells[i].excess -= transfer;
deficit_cells[j].excess -= transfer;

if (excess_cells[i].excess == 0) i++;
if (deficit_cells[j].excess == 0) j++;
}

return moves;
}

Ergebnisse:
Der Code wurde erfolgreich kompiliert.
Das Folgende ist der Beispieltest und seine Ergebnisse. Nur ein Test bestanden.

Code: Select all

Example Test 01:
Input: [[1, 0, 1], [1, 3, 0], [2, 0, 1]]
Result: PASSED

Example Test 02:
Input: [[2, 0, 2], [1, 0, 0], [2, 1, 1]]
Result: FAILED
Actual Result: 6
Expected Result: 4

Example Test 03:
Input: [[0, 6, 0], [2, 0, 0], [0, 1, 0]]
Result: FAILED
Actual Result: 11
Expected Result: 9