C++: найти количество ходов для размещения маркеров в сетке ⇐ C++

[Anonymous]

Мне дали задание по C++, в ходе которого меня попросили найти количество ходов, необходимое для размещения камня на каждом квадрате сетки. Я нашел решение, но оно сработало только в 40% случаев. Пожалуйста, помогите мне найти решение. Ниже представлена ​​задача и мое решение.
Задание
Вам дана сетка 3 x 3, содержащая ровно девять камни внутри его клеток. В ячейке может находиться любое количество камней.
Каждым ходом вы можете перекладывать камень из одной клетки в другую, если две клетки имеют общую сторону.
Сетка описывается матрицей целых чисел A 3 x 3. Строки нумеруются от 0 до 2 сверху вниз. Столбцы нумеруются от 0 до 2 слева направо. A[K][J] представляет количество камней в ячейке, расположенной на пересечении K-й строки и J-го столбца.
Напишите функцию:
int solution(vector &A)
что с учетом матрицы A возвращает минимальное количество ходов, необходимое для размещения одного камня в каждой ячейке.
Примеры:

• Дано A =[[1, 0, 1], [1, 3, 0], [2, 0, 1 ]], функция должна возвращать 3. Мы можем переместить камень из (1, 1) в (0, 1), от (1, 1) к (1, 2) и от (2, 0) к (2, 1).

• < li>Дано A = [[2, 0, 2], [1, 0, 0], [2, 1, 1]], функция должна вернуть 4.

• При условии A = [ [0, 6, 0], [2, 0, 0], [0, 1, 0]], функция должна вернуть 9.

Решение
Напишите эффективный алгоритм для следующие предположения:

• A имеет 3 строки и 3 столбца;
• каждый элемент матрицы A представляет собой целое число в диапазоне [0, 9];
  < li>A содержит ровно 9 камней.

Ниже представлено мое решение, которое не сработало в 60 % случаев, когда я его тестировал.
#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[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.excess, deficit_cells[j].excess);

// Calculate Manhattan distance for movement
int row1 = excess_cells.index / 3, col1 = excess_cells.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.excess -= transfer;
deficit_cells[j].excess -= transfer;

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

return moves;
}

Результаты:
Код успешно скомпилирован.
Далее: Пример теста и его результаты. Пройден только один тест.
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


Подробнее здесь: https://stackoverflow.com/questions/793 ... -on-a-grid