c++ - 国际象棋骑士到达棋盘上某个位置的最小步骤数

Question

有一个无限的棋盘，
从控制台中，我们输入将有多少个示例，棋盘上有多少个国际象棋骑士，他们的起始位置(即，他们的位置)，以及骑士必须经过最少的步骤才能到达的点。

它应该是这样的:

2-

示例数

1-国际象棋骑士

的数量

5 5-起点

5 6-终点

2-国际象棋骑士

的数量

0 0-第一个骑士

的起点

1 0-第二个骑士

的起点

0 1-第一个骑士

的终点

1 1-第二个骑士

的终点

回答:

3-第一个示例

的答案

4-第二个示例

的答案

问题在于它无法解决问题，因为使用第一个数据集，一切都很好，但是使用第二个数据集，则无法得出正确的答案。
如果我们分开计算分数，那么第二个数据集中的答案是6(第一个骑士3个，第二个骑士3个)。
我猜想如何解决它，但它不起作用。

推测是，当第二个骑士开始移动时，它经过的点与第一个骑士通过的点相同(第二个示例)，并且如果第一个骑士已经在这些位置，则可能需要写下条件，然后第二个骑士不能再次通过它们。

第二个猜想是您需要写下棋盘的条件并使其不受限制，并使骑士走棋盘的负值。

这是示例照片(下):

请帮助，我将非常感谢!

#include <iostream>
#include <set>
#include <queue>
#include <climits>
using namespace std;

#define N 8

// Below arrays details all 8 possible movements 
// for a knight
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };

// Check if (x, y) is valid chess board coordinates
// Note that a knight cannot go out of the chessboard
bool valid(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return false;

    return true;
}

// queue node used in BFS
struct Node
{
    // (x, y) represents chess board coordinates
    // dist represent its minimum distance from the source
    int x, y, dist;

    // Node constructor
    Node(int x, int y, int dist = 0): x(x), y(y), dist(dist) {}

    // As we are using struct as a key in a std::set, 
    // we need to overload < operator
    // Alternatively we can use std::pair<int, int> as a key
    // to store coordinates of the matrix in the set

    bool operator<(const Node& o) const
    {
        return x < o.x || (x == o.x && y < o.y);
    }
};

// Find minimum number of steps taken by the knight 
// from source to reach destination using BFS
int BFS(Node src, Node dest)
{
    // set to check if matrix cell is visited before or not
    set<Node> visited;

    // create a queue and enqueue first node
    queue<Node> q;
    q.push(src);

    // run till queue is not empty
    while (!q.empty())
    {
        // pop front node from queue and process it
        Node node = q.front();
        q.pop();

        int x = node.x;
        int y = node.y;
        int dist = node.dist;

        // if destination is reached, return distance
        if (x == dest.x && y == dest.y)
            return dist;

        // Skip if location is visited before
        if (!visited.count(node))
        {
            // mark current node as visited
            visited.insert(node);

            // check for all 8 possible movements for a knight
            // and enqueue each valid movement into the queue
            for (int i = 0; i < 8; ++i) 
            {
                // Get the new valid position of Knight from current
                // position on chessboard and enqueue it in the 
                // queue with +1 distance
                int x1 = x + row[i];
                int y1 = y + col[i];

                if (valid(x1, y1))
                    q.push({x1, y1, dist + 1});
            }
        }
    }

    // return INFINITY if path is not possible
    return INT_MAX;
}

// main function
int main()
{
    // source coordinates
    Node src = {0, 7};

    // destination coordinates
    Node dest = {7, 0};

    cout << "Minimum number of steps required is " << BFS(src, dest);

    return 0;
}

Answer 1

假设终点位置未链接到骑士(任何骑士都可以以任何终点位置结束)，这是一个答案。这是一个与编程语言无关的算法问题，因此我不会显示任何代码。

最简单但效率最低的方法是假设每个骑士都有一个所需的最终位置。您通过索引将最终位置的所有排列分配给骑士，并为每个排列计算结果。最后，您返回最小结果。在您的示例中，一个结果将是6(原始映射)，另一个结果将是4(交换最终位置，唯一的其他排列)，因此您将获得4。这种方法的问题是，对于n个骑士，您将拥有n个!排列考虑。

贪婪的方法是让每个骑士移动直到到达最后一个地点，然后让另一个跳到另一个地点。这将对您的示例有效，但在此示例中会出错:

Knights:(5,4)，(2,1);最终位置:(3,3)，(9,6)

第一个骑士会移动

(5,4)->(3,3)

完成(1步)，然后第二个骑士必须移动

(2,1)->(4,2)->(5,4)->(7,5)->(9,6)

这需要4个步骤，总共需要 5。但是，最佳解决方案是:

(5,4)->(7,5)->(9,6)

(2,1)->(3,3)

这是3个步骤。因此，我们看到，幼稚的贪婪算法不一定能产生正确的结果。

但是，我们可以采用贪婪的方法做得更好:首先，计算每个骑士/最终位置对之间的距离，并存储它们(使用原始算法)。

我们之前的示例如下所示:

(5,4)        <- first knight
  (3,3) = 1  <- distance to first final position
  (9,6) = 2  <- distance to second final position
(2,1)        <- second knight
  (3,3) = 1
  (9,6) = 4

一旦计算出这些位置，算法便会为骑士分配一个终点位置。它将像这样工作:

循环所有尚未结束的骑士。对于每个骑士，标记最近的最终位置并计算其他骑士的罚分。罚金是尚未分配的所有其他骑士的附加 Action 的最大值。例如，在 (3,3)上为骑士选择 (5,4)将会受到3的惩罚，因为另一个骑士现在将需要再移动3步(因为我们标记了其最近的最终位置)。但是，在 (3,3)上为骑士选择 (2,1)的惩罚为1，因为另一个骑士只需要再移动一个步骤即可。

计算完所有罚分后，将罚分最小的骑士分配给其最近的最终位置。循环直到所有骑士都被分配了最终位置。

这个算法对于您的原始示例和我的示例都是正确的，但是我不知道它是否总是正确的。您需要证明这一点。