用于表示地理表面的地形图的2D阵列的算法

I'm having difficulty figuring out what to do with the following problem

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

The input will be 2D array A[n][n] numbers, representing the topographic map of the geographic surface. Also among the input will be a starting location (r,c). referring to entry A[r][c]

输入将是2D阵列A [n] [n]数字,表示地理表面的地形图。输入中还将是起始位置(r,c)。参考条目A [r] [c]

If you were planning hiking trails you would be bound by the differences in elevation between neighboring entries. A person could traverse between 2 adjacent locations, if their elevations differ by no more than 2). Adjacency follows just the 4 standard compass directions, (so I assume no diagonals). Therefore , a point on the map is considered reachable if it is traversable from A[r][c] through any sequence of adjacent entires.

如果您计划远足径,您将受到相邻条目之间的高度差异的约束。如果一个人的高度相差不超过2,则可以在两个相邻位置之间穿越。邻接仅遵循4个标准罗盘方向(因此我假设没有对角线)。因此,如果地图上的点可以从A [r] [c]到任何相邻的entires序列遍历,则认为它是可到达的。

Write an algorithm that computes all of the reachable locations. The output will be another 2D array R[n][n] with true/fals values. (I assume true means reachable, false means unreachable)

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

If i understand this question correctly, I can create following matrix. (suppose A[10][10] looks like this from A[0][0]:)

如果我正确理解这个问题,我可以创建以下矩阵。 (假设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

Both south and east are traversable from A[0][0] so reachable entries would be:

南部和东部都可以从A [0] [0]遍历,因此可达到的条目将是:

50 51 54 58 60 60 60 63 68 71

48 52 51 59 60 60 63 63 69 70

48 52 51 59 60 60 63 63 69 70

44 48 52 55 58 61 64 64 66 69

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

38 42 46 56 56 63 64 61 64 62

36 40 44 50 58 60 66 65 62 61

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

30 36 40 47 50 64 64 63 62 60

50 50 50 50 50 50 50 50 50 50

so I can conclude that my resulting array should be

所以我可以断定我的结果数组应该是

1 1 0 0 0 0 0 1 0 0

1 1 0 0 0 0 0 1 0 0

1 1 1 0 0 0 1 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 0 0 0 1 1 1 0

0 0 1 1 0 0 0 0 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 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 1 1

0 0 0 0 1 1 0 0 0 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 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0

I want to implement this in c code but i think its improper to ask for the code here. My plan is to implement this in pseudocode first then implementing in c code, which I will try doing it by myself =). I'm not sure as to where to start with my pseudocode. Can anyone please clarify this?

我想用c代码实现这个,但我觉得在这里要求代码是不合适的。我的计划是首先在伪代码中实现它,然后在c代码中实现,我将尝试自己做=)。我不知道从哪里开始我的伪代码。有人可以澄清一下吗?

Thank you very much!

非常感谢你!

p.s just edited my matrix

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

1 个解决方案

#1

Have a look at Dijkstra or A-Star which are used in such a case. Further more you may have a look at Graph Theory basics in order to create an appropriate representation of your matrics.

看看在这种情况下使用的Dijkstra或A-Star。您还可以查看图论基础知识,以便创建适合您的matrics的表示。

Additionally you may need the Manhatten Distance which can be used as a heuristic for the A-Star in your case.

此外,您可能需要Manhatten Distance,可以在您的情况下用作A-Star的启发式。

There are many other algorihms if you dive deeper into the topic of graph theory and search algorithms.

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

EDIT due to comment:

编辑评论:

You can also use Depth First Search (DFS) or Breadth First Search (BFS). These algorithms are simpler to implement especially at the beginning.

您还可以使用深度优先搜索(DFS)或广度优先搜索(BFS)。这些算法在开始时更容易实现。

At first you need to create an appropriate datastructur which represents the hightmap. These structur could look like this:

首先,您需要创建一个代表hightmap的相应数据结构。这些结构可能如下所示:

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

after that you can use the following pseudocode as an proposal taken from Breadth first search and depth first search which already is aware of cycles within the graph, which would lead to infinite loops.

之后,您可以使用以下伪代码作为从广度优先搜索和深度优先搜索中获取的提议,该搜索已经知道图中的循环,这将导致无限循环。

 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
        }
    }

Some steps are missing within the pseudocode. For example the condition for abandon the DFS when visiting the goal.

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

Some additional notes:

一些额外的说明:

the DFS will find just a solution for your problem

DFS将为您的问题找到解决方案

Dijkstra and A-Star will find the shortest (optimal) solution for the problem (shortest path from start to goal, taking into account the hight of your Vertices

Dijkstra和A-Star将找到问题的最短(最佳)解决方案(从开始到目标的最短路径,考虑到顶点的高度)

#1