如何在C中遍历数组并找到所有可达点？
如何在C中遍历数组并找到所有可达点？
提问于 2017-03-02 12:49:16
我一直在思考如何从给定的起点Arrx找到数组中的所有可达点，其中可达点是指与当前位置值相差不超过2的点。然后我想返回一个数组，它在所有可及位置都有1，在不可达位置有0。
假设Arr6看起来像这样：
10 11 14 18 20 20
11 12 11 19 20 20
24 28 12 15 18 31
44 46 13 12 57 30
42 45 10 14 59 31
38 42 46 16 16 23则返回的数组将如下所示
1 1 0 0 0 0
1 1 1 0 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 1 0 0
0 0 0 1 1 0我认为实现这一点的最好方法是创建一个newArr，然后有4种不同的情况，将当前位置与其相邻位置进行比较，然后如果它们是可到达的，则将newArrx设置为1。否则将其设置为0。有人能解释一下我如何确定下一步要移动到哪里，以及如何跟踪我已经测试过的点吗？
考虑在原始数组中的位置，经过比较，既然有可能向右或向下移动，我该如何决定？还是两者兼而有之？
Stack Overflow用户
发布于 2017-03-02 13:20:41
你走在正确的道路上。是的，你需要检查一下邻居。您可以根据与所有4个邻居(或更少的邻居，取决于位置)的比较来做出决定。
这是一个典型的BFS问题。Look here和here.You从一个点开始，然后转到邻居处进行检查(这取决于您正在解决的问题)，并更新结果矩阵并继续进行。
通常，队列用于实现BFS。下面是算法：
Set result [n][n] as all zero
Insert the beginning point (i,j) to a queue Q
result[i][j] = 1 // the starting point is reachable from itself
While queue is not empty:
Take point (x,y) from Q
For each neighbor (z,w) of (x,y): //which are north, south, east, west
if (result[z][w] == 0 && | value[x][y] - value[z][w] | <= 2) {
result[z][w] = 1
push point(z,w) into Q
}更新1:感谢@Jonathan Leffler的评论，指出了8个邻居，而不是4个，以及value[x][y] - value[z][w] != 0可能的额外情况，需要@Shayna Grose确认
更新2:恢复。根据@Shayna Grose的评论:对角线是不允许的(需要考虑4个邻居)，diff =0是可以的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42547101
复制相关文章
相似问题
腾讯云开发者
