国际象棋骑士到达棋盘上某一位置的最少步数
The minimum number of steps for a chess knight to reach a certain position on a chessboard
棋盘无限，
我们从控制台输入将有多少个例子，棋盘上有多少个国际象棋骑士，以及他们的起始位置（即他们所在的位置），以及骑士必须以最少步数到达的点。
它应该是这样的：
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;
}
根据你给的数据，这两个骑士应该是这样走的：
- 第一个骑士：(0,0) -> (0,1)
- 第二个骑士：(1,0) -> (1,1)
但是，在您的图表中，您暗示骑士应该像这样移动（忽略缺少 1 的错误 x 轴）：
- 第一个骑士：(0,0) -> (1,1)
- 第二个骑士：(0,1) -> (1,0)
你的图表将每个马移动到 other 马的最终位置，这是不正确的。您的代码给出了 6，将每个骑士移动到您提供的数据所指示的最终位置的正确解决方案。
这是假设结束位置与骑士无关的答案（任何骑士都可以在任何结束位置结束）。这是一个独立于编程语言的算法题，所以我不会展示任何代码。
最简单但效率最低的方法是假设每个骑士都有一个必需的最终位置。您通过索引将最终位置的所有排列分配给骑士，并为每个排列计算结果。最后，你 return 最小的结果。在您的示例中，一个结果将是 6（原始映射），另一个结果将是 4（交换最终位置，唯一的其他排列），因此您将得到 4。这种方法的问题在于，对于 n 个骑士，您需要考虑 n! 个排列。
贪婪的方法是让每个骑士移动直到它到达最后一个点，然后另一个跳到另一个。这对你的例子有用，但对这个例子来说是错误的：
- 骑士：(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 个步骤。所以我们看到，朴素的贪心算法不一定会产生正确的结果。
但是，我们可以使用贪婪的方法做得更好：首先，计算每个 knight/final 位置对之间的距离，并存储它们（使用您的原始算法）。
我们之前的示例如下所示：
(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
计算完这些后，算法随后会为骑士分配一个结束位置。它会像这样工作：
遍历所有还没有结束位置的马。对于每个马，标记最近的最终位置并计算对其他马的惩罚。惩罚是所有其他尚未分配的骑士的额外移动的最大值。例如，为位于 (5,4) 的骑士选择 (3,3) 将会有 3 的惩罚，因为另一个骑士现在需要额外移动 3 步（因为我们标记了它最近的最终位置）。但是，为 (2,1) 的骑士选择 (3,3) 会受到 1 的惩罚，因为另一个骑士只需要多移动一步。
计算完所有惩罚后，将惩罚最小的骑士分配到最近的最终位置。循环直到所有骑士都被分配了最终位置。
这个算法对你原来的例子和我的例子都是正确的，但我不知道它是否总是正确的。你需要证明这一点。
棋盘无限，
我们从控制台输入将有多少个例子，棋盘上有多少个国际象棋骑士，以及他们的起始位置（即他们所在的位置），以及骑士必须以最少步数到达的点。
它应该是这样的：
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;
}
根据你给的数据，这两个骑士应该是这样走的：
- 第一个骑士：(0,0) -> (0,1)
- 第二个骑士：(1,0) -> (1,1)
但是，在您的图表中，您暗示骑士应该像这样移动（忽略缺少 1 的错误 x 轴）：
- 第一个骑士：(0,0) -> (1,1)
- 第二个骑士：(0,1) -> (1,0)
你的图表将每个马移动到 other 马的最终位置，这是不正确的。您的代码给出了 6，将每个骑士移动到您提供的数据所指示的最终位置的正确解决方案。
这是假设结束位置与骑士无关的答案（任何骑士都可以在任何结束位置结束）。这是一个独立于编程语言的算法题，所以我不会展示任何代码。
最简单但效率最低的方法是假设每个骑士都有一个必需的最终位置。您通过索引将最终位置的所有排列分配给骑士，并为每个排列计算结果。最后，你 return 最小的结果。在您的示例中，一个结果将是 6（原始映射），另一个结果将是 4（交换最终位置，唯一的其他排列），因此您将得到 4。这种方法的问题在于，对于 n 个骑士，您需要考虑 n! 个排列。
贪婪的方法是让每个骑士移动直到它到达最后一个点，然后另一个跳到另一个。这对你的例子有用，但对这个例子来说是错误的：
- 骑士：(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 个步骤。所以我们看到，朴素的贪心算法不一定会产生正确的结果。
但是，我们可以使用贪婪的方法做得更好：首先，计算每个 knight/final 位置对之间的距离，并存储它们（使用您的原始算法）。
我们之前的示例如下所示：
(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
计算完这些后，算法随后会为骑士分配一个结束位置。它会像这样工作：
遍历所有还没有结束位置的马。对于每个马，标记最近的最终位置并计算对其他马的惩罚。惩罚是所有其他尚未分配的骑士的额外移动的最大值。例如，为位于 (5,4) 的骑士选择 (3,3) 将会有 3 的惩罚，因为另一个骑士现在需要额外移动 3 步（因为我们标记了它最近的最终位置）。但是，为 (2,1) 的骑士选择 (3,3) 会受到 1 的惩罚，因为另一个骑士只需要多移动一步。
计算完所有惩罚后，将惩罚最小的骑士分配到最近的最终位置。循环直到所有骑士都被分配了最终位置。
这个算法对你原来的例子和我的例子都是正确的，但我不知道它是否总是正确的。你需要证明这一点。