CODEWITHSUNDEEP
carraysalgorithmmultidimensional-array
Newbie18
Newbie18

Reputation: 171

How to traverse an array and find all reachable points in C?

I've been thinking about how to find all the reachable points in an array from a given starting point Arr[x][y], where reachable points are points that values differ by no more than 2 from the current positions value. Then I want to return an array which has 1's in all reachable positions and 0's in unreachable positions.

Suppose Arr[6][6] looks like this:

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

Then the returned array would look like

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

I'm thinking the best way to achieve this is to create a newArr and then have 4 different cases where I compare the current position to each of its neighbours, and then if they are reachable, set newArr[x][y] to a 1. Otherwise set it to a 0. Can someone explain how I determine where to move to next, and how to keep track of which points I've already tested?

Consider position [0][0] in the original array, after comparisons, since it is possible to move right or down, how do I decide? Or somehow do both?

Upvotes: 2

Views: 901

Answers (3)

guanjun
guanjun

Reputation: 39

I think you can use a DFS(Depth-first search)to slove this problems.and I think BFS is also OK. c code:

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

Upvotes: 0

vim_
vim_

Reputation: 2170

You are on the right path. Yes, you need to check the neighbors. You make a decision based on the comparison with all 4 neighbors(or less depending on the location).

This is a typical BFS problem. Look here and here.You start from one point, then go to the neighbor and do a check (which depends on the problem that you are solving), and update a result matrix and keep going on.

Typically a queue is used for implementing BFS. Here is the algorithm:

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
       }

[UPDATED 1]: Thanks for comment from @Jonathan Leffler for pointing out 8 neighbors, not 4, and the possible extra condition of value[x][y] - value[z][w] != 0 that needs to be confirmed by @Shayna Grose

[UPDATED 2]: Reverting back. Per @Shayna Grose comment: Diagonal is not allowed (4 neighbors need to be taken into account) and the diff = 0 is OK.

Upvotes: 3

codehearts
codehearts

Reputation: 505

You might want to consider something like a flood fill algorithm. Your "target color" would be the value of your starting point, and your "replacement color" would be any point within ±2 of the target. Rather than "painting" your data array, you instead want to mark the indices in the return array. calloc is good choice for initially zeroing out your return array.

After evaluating your starting point, you would evaluate the indices adjacent to that index. If an index has been marked as 1 in the array you're returning, you can ignore that index because it's already been covered by the algorithm.

Upvotes: 4

Related Questions