如何在C中遍历数组并找到所有可达点？
我一直在思考如何从给定的起点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。有人能解释一下我如何确定下一步要移动到哪里，以及如何跟踪我已经测试过的点吗？
考虑在原始数组中的位置，经过比较，既然有可能向右或向下移动，我该如何决定？还是两者兼而有之？
回答 3
Stack Overflow用户
发布于 2017-03-02 12:58:54
您可能需要考虑flood fill算法之类的东西。您的“目标颜色”将是您的起始点的值，而您的“替换颜色”将是目标的±2范围内的任何点。与其“绘制”数据数组，不如标记返回数组中的索引。calloc是最初将返回数组置零的好选择。
在评估您的起点之后，您将评估与该指标相邻的指标。如果一个索引在你返回的数组中被标记为1，你可以忽略这个索引，因为它已经被算法覆盖了。
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用户
发布于 2017-03-02 16:44:01
我认为你可以使用深度优先搜索来解决这个problems.and，我认为深度优先搜索也是可以的。C代码：
#include <stdio.h>
int row,col,x,y;
int a[6][6]={
50,51 ,54, 58, 60, 60,
48, 52, 51, 59, 60, 60,
44, 48, 52, 55, 58, 61,
44, 46, 53, 52, 57, 60,
42, 45, 50, 54, 59, 61,
38, 42, 46, 56, 56, 63
};// the date
int vis[6][6];// the result
int dir[4][2]={
1,0,0,1,0,-1,-1,0
};
void dfs(int x,int y){
for(int i=0;i<4;i++){ //4 direction
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(!vis[nx][ny]&&abs(a[nx][ny]-a[x][y])<=2&&nx>=0&&ny>=0&&nx<6&&ny<6){
vis[nx][ny]=1;
dfs(nx,ny);
}
}
}
int main()
{
vis[6][6]={0};
scanf("%d%d",&x,&y);
vis[x][y]=1;
dfs(x,y);
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
printf("%d",vis[i][j]);
}
printf("\n");
}
return 0;
}https://stackoverflow.com/questions/42547101
复制相似问题
腾讯云开发者
