开发者

Get adjacent elements in a two-dimensional array?

开发者 https://www.devze.com 2022-12-16 11:05 出处:网络
I have a two-dimensional array, say 0 0 0 0 0 0 2 3 4 0 0 9 1 5 0 0 8 7 6 0 0 0 0 0 0 开发者_StackOverflowAnd i need to get all the numbers adjacent to 1(2, 3, 4, 5, 6, 7, 8, 9)

I have a two-dimensional array, say

0 0 0 0 0
0 2 3 4 0
0 9 1 5 0
0 8 7 6 0
0 0 0 0 0

开发者_StackOverflowAnd i need to get all the numbers adjacent to 1(2, 3, 4, 5, 6, 7, 8, 9)

Is there a less ugly solution than:

topLeft = array[x-1][y-1]
top  = array[x][y-1]
topRight = array[x+1][y-1]
# etc

Thanks!


If you're not worried about the order, the cleanest is probably to use a couple of loops:

result = new List<int>(8);
for (dx = -1; dx <= 1; ++dx) {
    for (dy = -1; dy <= 1; ++dy) {
        if (dx != 0 || dy != 0) {
            result.Add(array[x + dx][y + dy]);
        }
    }
}

If the order is important, you can construct a list of all the (dx, dy) in the order you want and iterate over that instead.

As pointed out in the comments, you probably want to add boundary checks. You could do that like this (assuming order doesn't matter):

List<int> result = new List<int>(8);
for (int dx = (x > 0 ? -1 : 0); dx <= (x < max_x ? 1 : 0); ++dx)
{
    for (int dy = (y > 0 ? -1 : 0); dy <= (y < max_y ? 1 : 0); ++dy)
    {
        if (dx != 0 || dy != 0)
        {
            result.Add(array[x + dx][y + dy]);
        }
    }
}


I'd probably go for a constant list of dx, dy for each direction, like so:

struct {
    int dx;
    int dy;
} directions[] = {{-1,-1,},{-1,0,},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

Then you'd iterate over the directions using a simple loop:

for (int i = 0; i < 8; i++) {
    // use x + directions[i].dx;
    // use y + directions[i].dy;
}

You can of course use sizeof(directions) / sizeof(directions[1]) instead of the 8 above.


personally, the loops are more ugly than the original.

topLeft  = array[ x - 1 ][ y - 1 ]
top      = array[ x     ][ y - 1 ]
topRight = array[ x + 1 ][ y - 1 ]

midLeft  = array[ x - 1 ][ y     ]
midRight = array[ x + 1 ][ y     ]

botLeft  = array[ x - 1 ][ y + 1 ]
bot      = array[ x     ][ y + 1 ]
botRight = array[ x + 1 ][ y + 1 ]

But without specifying what you want the values for - what you do in the different directions implies whether you want the values in separate variables or not.

For game of life style processing, you usually want to be working on a bitpattern anyway rather than an array of individual values, and you can scan horizontally inspecting only three of the eight cells at a time using accumulators and temporaries. For graphics convolutions, use an existing library with a 3x3 kernel.

The other way of dealing with boundaries is to expand the array by one cell in each direction. This avoids expensive branches in the convolution code.


python generator to get the adjacent nodes in a given matirx

def gen_adjacent_node(matrix_2d, node=(0,0)):
    rows = len(matrix_2d)
    columns = len(matrix_2d[0])
    for r in [-1, 0, 1]:
        for c in [-1, 0, 1]:
            if r == c == 0:
                continue
            # check valid index
            if 0 <= node[0]+r < rows and 0 <= node[1]+c < columns:
                # print((node[0]+i, node[1]+j))
                yield (node[0]+r, node[1]+c)


In C++ this can look like:

vector<int> adj;
for (int i = 0; i < 9; i++)
  if (i != 4) adj.push_back(array[x + i/3 - 1][y + i%3 - 1]);

This is not very clear solution but very short.


Here's a Ruby solution. The algorithm should be evident even for readers who are not familiar with Ruby. Note how I've computed the rows and columns to be iterated over (which would be written similarly in most languages). This seems to me much cleaner than, for example, "from max(r-1, 0) to min(r+1, arr.size-1)" for the indices of the rows to iterate.

def adjacent(arr, r, c)
  rows_ndx = arr.each_index.select { |i| (i-r).abs < 2 }
  cols_ndx = arr.first.size.times.select { |j| (j-c).abs < 2 }
  rows_ndx.each_with_object([]) do |i,a| 
    cols_ndx.each { |j| a << arr[i][j] unless [i,j] == [r,c] }
  end
end

arr = [
  [-1,  2,  3,  4],
  [-2,  9,  1,  5],
  [-3,  8,  7,  6],
  [-4, -5, -6, -7]
]

(0..2).each do |i|
  (0..3).each do |j|
    puts "adjacent to #{arr[i][j]} at r=#{i}, c=#{j} = #{adjacent(arr, i, j)}"
  end
end

prints

adjacent to -1 at r=0, c=0 = [2, -2, 9]
adjacent to  2 at r=0, c=1 = [-1, 3, -2, 9, 1]
adjacent to  3 at r=0, c=2 = [2, 4, 9, 1, 5]
adjacent to  4 at r=0, c=3 = [3, 1, 5]
adjacent to -2 at r=1, c=0 = [-1, 2, 9, -3, 8]
adjacent to  9 at r=1, c=1 = [-1, 2, 3, -2, 1, -3, 8, 7]
adjacent to  1 at r=1, c=2 = [2, 3, 4, 9, 5, 8, 7, 6]
adjacent to  5 at r=1, c=3 = [3, 4, 1, 7, 6]
adjacent to -3 at r=2, c=0 = [-2, 9, 8, -4, -5]
adjacent to  8 at r=2, c=1 = [-2, 9, 1, -3, 7, -4, -5, -6]
adjacent to  7 at r=2, c=2 = [9, 1, 5, 8, 6, -5, -6, -7]
adjacent to  6 at r=2, c=3 = [1, 5, 7, -6, -7]


#include <iostream>
using namespace std;

bool isValidPos(int i, int j, int n)
{
    if (i < 0 || j < 0 || i > n - 1 || j > n - 1)
        return 0;

    return 1;
}

void adjacentElements(int arr[][3], int i, int j)
{
    int n = 3;
    // first row
    if (isValidPos(i - 1, j - 1, n))
        cout << i - 1 << j - 1 << " ";
    if (isValidPos(i - 1, j, n))
        cout << i - 1 << j << " ";
    if (isValidPos(i - 1, j + 1, n))
        cout << i - 1 << j + 1 << " ";
    // second row
    if (isValidPos(i, j - 1, n))
        cout << i << j - 1 << " ";
    if (isValidPos(i, j + 1, n))
        cout << i << j + 1 << " ";
    // third row
    if (isValidPos(i + 1, j - 1, n))
        cout << i + 1 << j - 1 << " ";
    if (isValidPos(i + 1, j, n))
        cout << i + 1 << j << " ";
    if (isValidPos(i + 1, j + 1, n))
        cout << i + 1 << j + 1 << " ";
}

int main()
{
    int arr[3][3] = {0};

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {

            cout << i << j << " "
                 << " = [ ";
            adjacentElements(arr, i, j);
            cout << "]" << endl;
        }
        // cout << endl;
    }
}

output

00  = [ 01 10 11 ]
01  = [ 00 02 10 11 12 ]
02  = [ 01 11 12 ]
10  = [ 00 01 11 20 21 ]
11  = [ 00 01 02 10 12 20 21 22 ]
12  = [ 01 02 11 21 22 ]
20  = [ 10 11 21 ]
21  = [ 10 11 12 20 22 ]
22  = [ 11 12 21 ]


This was my solution facing a similar problem recently, with boundary checking. I find it more readable than some of the other suggestions here. You could embed the boundary checking into the loop, but I find this way more readable.

List<int[]> getSurroundingVals(int[][] array, int x, int y) {
    List<int[]> surroundingVals = new ArrayList<>();

    // Set offset indices to loop around the given cell coords
    row_min = Math.max(x - 1, 0);
    row_max = Math.min(x + 1, array.length - 1);
    col_min = Math.max(y - 1, 0);
    col_max = Math.min(y + 1, array[0].length - 1);

    // Loop through the surrounding cells and collect the values
    for (int i = row_min; i <= row_max; ++i) {
        for (int j = col_min; j <= col_max; ++j) {
            if (!(i == 0 && j == 0)) {
                surroundingVals.add(new int[]{array[x + i][y + j]});
            }
        }
    }
    
    return surroundingVals;
}
0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号