4x4 网格上的最短路径 C++

Question

我看到还有一个问题几乎是这样的，但是答案没有达到我想要的结果。

这是作业。我有一个 4x4 网格，用户输入了开始和结束 (x,y) 坐标。我需要将此信息从 main 发送到 create_path 函数，该函数计算最短路径，然后将其发送到另一个函数，该函数逐步打印标记位置的网格，直到到达所需的坐标。我不能使用数组，我必须有 main、create_path 和 print_path。标记只能上、下、左、右。

所以我真的不知道该怎么办。我考虑过为网格中的每个单元格创建一个变量，但不知道从那里去哪里。如果有人知道一个只使用 main 和另一个函数的快速解决方案，那没问题，因为我运行没时间了。

您不需要查看 main，因为它只是向用户显示网格并要求他们输入，然后将输入发送到此函数：

void create_path(int xStart, int xEnd, int yStart, int yEnd)
{

}

Answer 1

create_path 必须是递归函数。

给定的条件应该是：

首先检查点是否在边界内
然后检查该点是否是想要的点，如果是则return
否则递归上、下、左、右和对角点。

Answer 2

正如您已经在评论中指出的那样，从 (0,2) 到 (3,1) 的最短路径是 "right 3 down 1" 换句话说：右 3-0=3 和下 2 -1=1

这已经差不多是答案了...

一般来说，如何找到从(xStart, yStart) 到(xEnd, yEnd) 的最短路径？您只需再次执行与以前相同的操作。是"right xEnd-xStart, down yEnd-yStart".

所以 print_path 函数需要的一切只是 "where do I start" 和 "how much do I go right/left and how much do I go up/down?"

所以你可以在 create_path

中使用两个变量

int right = xEnd-xStart;
int down = yEnd-yStart;

然后你将这些发送给 print_path。您尚未提供 print_path 的签名，但它可能如下所示：

void print_path(int xStart, int yStart, int right, int down) 
{

}

在此函数中，您只需执行两个循环：

int i = xStart;
int xend = xStart + right; // observe: if right is negative, it's just subtraction
bool right = (right >= 0); // are we going right or left?

while(i != xend) {
     std::cout << "next waypoint: x = " << i << ", y = " << yStart << std::endl;
     if (right) {
          i++;
     } else {
          i--;
     }
}

现在你对 y 坐标做同样的事情

int j = yStart;
int yend = yStart + down; 
bool down = (down >= 0); // are we going down or up?

while(j != yend) {
     std::cout << "next waypoint: x = " << xend << ", y = " << j << std::endl;
     if (down) {
          j++;
     } else {
          j--;
     }
}

4x4 网格上的最短路径 C++

Shortest path on 4x4 grid c++

c++

shortest-path