C++ 查找在网格上放置标记的移动次数

Question

我参加了一项 C++ 评估，要求我找出在网格的每个方格上放置一块石头所需的移动次数。我想出了一个解决方案，但只成功了 40%。请帮我找到解决方案。以下是任务和我的解决方案。

任务

您将获得一个 3 x 3 的网格，其中的单元格中恰好包含九颗石头。一个单元格可以包含任意数量的石头。

在每次移动中，如果两个格子有共同的一面，则可以将石头从一个格子移到另一个格子。

网格由整数 A 的 3 x 3 矩阵描述。行从上到下从 0 到 2 编号。列从左到右编号为 0 到 2。 A[K][J]表示位于第K行和第J列交叉点的单元格中的棋子数量。

编写一个函数：

 int solution(vector<int> &A)

给定矩阵 A，返回在每个单元格中放置一颗石头所需的最小移动次数。

示例：

1. 给定 A =[[1, 0, 1], [1, 3, 0], [2, 0, 1]]，函数应返回 3。我们可以将石头从 (1, 1) 移至 (0 , 1)、从 (1, 1) 到 (1, 2) 以及从 (2, 0) 到 (2, 1)。

示例一网格

2. 给定 A = [[2, 0, 2], [1, 0, 0], [2, 1, 1]]，该函数应返回 4。

示例两个网格

3. 给定 A = [[0, 6, 0], [2, 0, 0], [0, 1, 0]]，该函数应返回 9。

三网格示例

解决方案

针对以下假设编写一个有效的算法：

• A 有 3 行 3 列；
• 矩阵A的每个元素都是[0, 9]范围内的整数；
• A 正好包含 9 颗宝石。

以下是我的解决方案，在我的测试中 60% 的时间都失败了。

#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

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

    vector<Cell> 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;
}

结果：

代码编译成功。

以下是示例测试及其结果。仅通过一项测试。

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 

Answer 1

在 3x3 网格中，每块移动的石头都可以通过一步或两步到达其最终位置 - 它可以在 1 步中移动到相邻单元格，也可以在 2 步中移动到任何其他单元格（通过遍历如果需要的话中间。

要找到最佳移动次数，您需要最大化 1 步中移动的石子数量。

制作一个二分图，一侧有多余的石头，另一侧有缺失的石头（缺陷），然后将每个多余的石头连接到相邻单元格中的所有缺陷。

现在在这个图中找到一个最大匹配（谷歌最大二分匹配），这将给出1步移动的总数。

最小移动次数就是

total_deficits*2 - number_of_1_steps