c-表示地理表面地形图的2D阵列的算法

Question

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

输入将是2D阵列A[n][n]数字，表示地理表面的地形图。输入中还将有一个起始位置（r，c）。参考条目A[r][c]

如果你计划徒步旅行，你会受到相邻入口之间海拔差异的限制。一个人可以在两个相邻的位置之间穿行，如果它们的海拔相差不超过2）。相邻仅遵循4个标准指南针方向（所以我假设没有对角线）因此，如果地图上的一个点可以从a[r][c]穿过任何相邻整数序列，则该点被认为是可达的。

编写一个算法来计算所有可到达的位置。输出将是另一个具有真/假值的2D阵列R[n][n]。（我认为true表示可达，false表示不可达）

如果我正确理解这个问题，我可以创建以下矩阵。（假设A[10][10]在A[0][0]中看起来是这样的：）

50 51 54 58 60 60 63 68 71

48 52 51 59 60 60 63 63 69 70

44 48 52 55 58 61 64 66 69

44 46 53 52 57 60 61 65 68

42 45 50 54 59 61 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 63 62 60

50 50 50 50

南部和东部均可从A[0][0]穿过，因此可到达的条目为：

50 5154 58 60 606368 71

48 52 5159 60 6063 6369 70

44 485255 58 6164 64 6669

44 46535257 60 616568

42 45 505459 61 63 636670

38 42 46565663 64 6164 62

36 40 44 50586066 6562 61

36 39 42 49566267 66 6560

30 36 40 47 50646463 62 60

50 50 50 50

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

1 10 0 0 010 0

1 1 10 011 10 0

0 010 0 01 1 10

0 01 10 0 010

0 0 010 0 010

0 0 01 1 10 01 1

0 0 0 01 1 10 01 1

0 0 01 10 01

0 0 0 01 1 1 1

0 0 0 0

我想在c代码中实现这一点，但我认为在这里要求代码是不合适的。我的计划是先用伪代码实现，然后用c代码实现，我将尝试自己实现=）。我不确定从哪里开始使用我的伪代码。有人能澄清一下吗？

非常感谢！

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

Answer 1

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

此外，您可能需要曼哈顿距离，在您的情况下，该距离可以用作a-Star的启发式。

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

因评论而编辑：

您也可以使用深度优先搜索（DFS）或广度优先搜索（BFS）

首先，您需要创建一个适当的数据结构来表示高度图。这些结构可能看起来像这样：

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

之后，您可以使用以下伪代码作为来自广度优先搜索和深度优先搜索的建议它已经知道图中的循环，这将导致无限循环。

 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将找到问题的最短（最佳）解决方案（从开始到目标的最短路径，考虑顶点的高度