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

Question

我很难弄清楚如何处理以下问题

输入将是二维数组A[n][n]个数，代表地理表面的地形图。输入中还有一个起始位置 (r,c)。参考条目 A[r][c]

如果您计划徒步旅行，您会受到相邻条目之间的海拔差异的约束。一个人可以在 2 个相邻位置之间穿行，如果它们的海拔相差不超过 2)。邻接仅遵循 4 个标准罗盘方向，（所以我假设没有对角线）。 因此，如果地图上的一个点可以从 A[r][c] 穿越到任何相邻的序列。

编写一个算法来计算所有可到达的位置。输出将是另一个具有 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 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 or A-Star。此外，您还可以查看图论基础知识，以便创建适当的矩阵表示。

此外，您可能需要 Manhatten Distance，它可用作您案例中 A-Star 的 heuristic。

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

因评论而编辑：

您也可以使用Depth First Search (DFS) or 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 将找到问题的最短（最佳）解决方案（从开始到目标的最短路径，取考虑到你的顶点的高度

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

algorithm for 2D array that represents the topographic map of geographic surface

c

dijkstra

multidimensional-array

graph-algorithm

data-structures