CODEWITHSUNDEEP
c++algorithm
Syntactic Fructose
Syntactic Fructose

Reputation: 20084

C++ 2 Dimensional Map find all adjacent squares to given index

I'm having trouble thinking of an efficient way to find all adjacent squares to a given value in a 2d container. Say I have a container represented as:

. . . . .
. G . . .
. . . . .
. . . . .
. . . . G

now after the container is generated in my program(as it looks above), I need to set all adjacent squares of G to X, so the map should look like:

X X X . .
X G X . .
X X X . .
. . . X X
. . . X G

I feel there is a much easier way than how I am currently going about this solution. Here's the thought process I have:

for r to container.size()
    for c to container.size()
        if r == 0                            //if we're at the first row, don't check above
            if c == 0                        //if we're at the first column, don't check to the left

            else if c == container.size() -1 //if we're at the last column, don't check to the right

        else if r == container.size()        //if we're at the last row, don't check below
            if c == 0                        //if we're at the first column, don't check to the left

            else if c == container.size() -1 //if we're at the last column, don't check to the right

        else if c == 0                       //if we're at the first column, don't check to the left

        else if c == container.size() - 1    //if we're at the last column, don't check to the right

        else                                 //check everything

this seem's reallllllly repetitive however, I have to check a lot of conditions to avoid accidently checking outside the bounds of my map. I'm going to be writing a lot of if(map[r][c+1] == "G") statements for each seperate if/else written above. Is there a different way to check if a square is adjacent to G that i'm not thinking of?

Upvotes: 1

Views: 694

Answers (3)

Jarod42
Jarod42

Reputation: 217398

A possible way to avoid checking out of the bound is to extend the matrix by one in each direction:

So you have something like

0 0 0 0 0 0 0
0 . . . . . 0
0 . G . . . 0
0 . . . . . 0
0 . . . . . 0
0 . . . . G 0
0 0 0 0 0 0 0

and then you just have to check to your special value if really you want to check or do your algorithm without check as above:

// index 0 and N + 1 are the surrounding
for (int x = 1; x != N + 1; ++x) {
    for (int y = 1; y != N + 1; ++y) {
        if (map[x][y] != 'G') {
            continue;
        }
        const int x_offsets[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        const int y_offsets[] = {-1, -1, -1, 0, 0, 1, 1, 1};

        for (int i = 0; i != 8; ++i) {
#if 0 // if you don't want to modify surrounding
            if (map[x + x_offsets[i]][y + y_offsets[i]] == BORDER_SPECIAL_VALUE) {
                continue;
            }
#endif
            map[x + x_offsets[i]][y + y_offsets[i]] = 'X';
        }
    }
}

Upvotes: 1

yogi
yogi

Reputation: 144

#define CHECK(x,y) x < 0 || x >= xsize || y < 0 || y >= ysize ? false : map[x,y]

for r to container.size()
    for c to container.size() 
        if CHECK(r-1,c-1)
            ...
        if CHECK(r-1,c)
            ...
        ...

Upvotes: 0

Paul R
Paul R

Reputation: 212979

One way to simplify this is to add a border to your data structure, so you have e.g.

char map[N+2][N+2];

Then iterate over the map like this:

for (i = 1; i <= N; ++i)
{
    for (j = 1; j <= N; ++j)
    {
        if (map[i][j] == 'G')
        {
            for (di = -1; di <= 1; ++di)
            {
                for (dj = -1; dj <= 1; ++dj)
                {
                    if (di == 0 && dj == 0)      // skip central value
                        continue;
                    map[i + di][j + dj] = 'X';   // set neighbouring values to 'X'
                }
            }
        }
    }
}

Upvotes: 1

Related Questions