Get adjacent elements in a two-dimensional array?
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;
}
精彩评论