c - 表示地理表面地形图的二维数组算法

Question

我很难弄清楚如何解决以下问题

输入将是二维数组 A[n][n] 数字，表示地理表面的地形图。输入中还有起始位置 (r,c)。引用条目 A[r][c]

如果您正在规划远足路线，您将受到相邻条目之间海拔差异的限制。如果两个相邻位置的海拔相差不超过 2)，则一个人可以在两个相邻位置之间移动。邻接仅遵循 4 个标准罗盘方向(所以我假设没有对角线)。因此，如果可以从 A[r][c] 通过任意序列遍历 map 上的点，则认为该点是可达的。相邻的整体。

编写一个算法来计算所有可到达的位置。输出将是另一个具有 true/fals 值的二维数组 R[n][n]。 (我假设 true 表示可达， false 表示不可达)

如果我正确理解这个问题，我可以创建以下矩阵。 (假设 A[10][10] 与 A[0][0] 看起来像这样:)

50 51 54 58 60 60 60 63 68 71

48 52 51 59 60 60 63 63 69 70

44 48 52 55 58 61 64 64 66 69

44 46 53 52 57 60 60 61 65 68

42 45 50 54 59 61 63 63 66 70

38 42 46 56 56 63 64 61 64 62

36 40 44 50 58 60 66 65 62 61

36 39 42 49 56 62 67 66 65 60

30 36 40 47 50 64 64 63 62 60

50 50 50 50 50 50 50 50 50 50

南部和东部都可以从 A[0][0] 穿过，因此可到达的条目将是:

50 51 54 58 60 60 60 63 68 71

48 52 51 59 60 60 63 63 69 70

44 48 52 55 58 61 64 64 66 69

44 46 53 52 57 60 60 61 65 68

42 45 50 54 59 61 63 63 66 70

38 42 46 56 56 63 64 61 64 62

36 40 44 50 58 60 66 65 62 61

36 39 42 49 56 62 67 66 65 60

30 36 40 47 50 64 64 63 62 60

50 50 50 50 50 50 50 50 50 50

所以我可以得出结论，我的结果数组应该是

1 1 0 0 0 0 0 1 0 0

1 1 1 0 0 0 1 1 0 0

0 0 1 0 0 0 1 1 1 0

0 0 1 1 0 0 0 0 1 0

0 0 0 1 0 0 0 0 1 0

0 0 0 1 1 0 0 0 1 1

0 0 0 0 1 1 0 0 1 1

0 0 0 0 1 1 0 0 0 1

0 0 0 0 0 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0

我想用c代码实现这个，但我认为在这里索要代码是不合适的。我的计划是首先用伪代码实现，然后用 C 代码实现，我将尝试自己完成 =)。我不确定从哪里开始我的伪代码。谁能澄清一下吗？

非常感谢!

p.s刚刚编辑了我的矩阵

Answer 1

看看Dijkstra或A-Star在这种情况下使用。此外，您还可以查看图论基础知识，以便创建适当的矩阵表示。

此外，您可能需要 Manhatten Distance在您的案例中，这可以用作 A-Star 的启发。

如果您深入研究图论和搜索算法主题，还有许多其他算法。

根据评论进行编辑:

您还可以使用Depth First Search (DFS)或Breadth First Search (BFS) 。这些算法更容易实现，尤其是在开始时。

首先，您需要创建一个代表高度图的适当数据结构。这些结构可能如下所示:

struct Vertex 
     int x                 // coordinate x
     int y                 // coordinate y
     Vertex neighbors[8]; // Array of all adjacent vertices 
     int height            // height
}

之后，您可以使用以下伪代码作为取自 Breadth first search and depth first search 的建议 它已经知道图中的循环，这会导致无限循环。

 dfs(vertex v) {
    visit(v); 
    for each neighbor w of v            
        if w is unvisited **and reachable** // reachable according to your hight differences
        {
        dfs(w); // recursive call to the dfs 
        add edge vw to tree T  //tree contains a result path in your
                               //case the second matrix
        }
    }

伪代码中缺少一些步骤。例如条件为 访问目标时放弃 DFS。

一些附加说明:

• DFS 将为您的问题找到解决方案
• Dijkstra 和 A-Star 将找到问题的最短(最佳)解决方案(从起点到目标的最短路径，考虑到顶点的高度