在二维尺寸数组中查找"trail"

Question

我不知道如何解决这个问题，我只是一个计算机科学的初学者。

输入为二维数组A[n][n]个数字，表示地理表面的地形图。在输入中也会有一个起始位置(r,c)。参考条目A[r][c]

如果你计划徒步旅行，你会受到相邻入口之间海拔差异的限制。一个人可以在两个相邻的地点之间穿行，如果它们的高度相差不超过2)。邻接只遵循4个标准罗盘方向(所以我假设没有对角线)。因此，如果映射上的一个点可以从a [r][c]穿过任何相邻的整体序列，则认为它是可到达的。

编写一个计算所有可到达位置的算法。输出将是另一个2D数组R[n][n]，具有true/fals值。(我假设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

我们的教授要求我们用伪代码实现这个。我不知道如何对相邻的两个点和点的四个方向进行比较。谁能给我一些建议?

Answer 1

只是填充物。您需要一个队列和一个可索引寻址的"已访问"标志向量。将根放入队列中。当队列不是空的时候，取第一个元素，检查可到达的位置N,S,E,W。然后检查他们是否被访问过。如果没有，则将其标记为已访问，并将其放入队列中。