如何获取二维数组中相邻的元素？

Question

我有一个二维数组，比如说

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

我需要获取与1相邻的所有数字（2、3、4、5、6、7、8、9）。

除了下面这个难看的方法，还有更好的解决方案吗？

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

谢谢！

- Ian P

Answer 1

如果不关心顺序，最简洁的方法可能是使用几个循环：

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]);
        }
    }
}

如果顺序很重要，您可以构建一个以您想要的顺序列出所有（dx，dy）的列表，并对其进行迭代。正如评论中指出的那样，您可能希望添加边界检查。如果顺序不重要，可以这样做：

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]);
        }
    }
}

- Mark Byers

---

你需要考虑边缘情况。如果（x，y）的规范是（0，0），那么你的数组索引将超出范围。由于这看起来像C#代码，这意味着你会得到一个异常。 - Eilon

如果将边界拉出来，代码会更加简洁。dxmin = x > 0 ? -1 : 0; dxmax = x < x_max ? 1 : 0。然后第一个for循环将变为for (int dx = dxmin; dx <= dxmax; dx++)。 - Maxareo

Answer 2

就我个人而言，循环比原来的代码更加丑陋。

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 ]

但如果没有明确指定您需要值的内容，那么在不同方向上所做的操作将决定您是否需要将值放入单独的变量中。

对于类似生命游戏的处理，通常更适合使用位模式而不是单独值的数组，并且可以使用累加器和临时变量一次性扫描水平方向上仅三个八个单元格。对于图形卷积，请使用具有3x3内核的现有库。

处理边界的另一种方法是在每个方向上将数组扩展一个单元格。这避免了在卷积代码中出现昂贵的分支。

- Pete Kirkham

---

在搜索其他内容时，我偶然发现了您的答案。非常好的解决方案。我想知道...如果数组像帕斯卡金字塔一样，是否可能应用类似的东西？不是“一个”帕斯卡金字塔，只是形状：顶部有一个条目，中间有两个条目，底部有三个条目？ - user753531

Answer 3

我会选择为每个方向设置一个(dx, dy)常量列表，像这样：

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

然后您可以使用简单的循环迭代方向：

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

当然，您可以使用sizeof(directions) / sizeof(directions[1])来代替上面的8。

- elifiner

---

这可能是最漂亮的实现。 - rw-nandemo

嗨，这里的 x 和 y 会是什么？谢谢。 - Unheilig

这很简洁，但在添加边界检查后，它可能会变得一样简洁。 - Maxareo

Answer 4

使用 Python 生成器获取给定矩阵中相邻节点。

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)

- Nandlal Yadav

---

由于yield是Python特定的运算符，您可能还可以包括如何使用/打印此函数的结果的示例？ - John Doe

Answer 5

在C++中，这可能看起来像这样：

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]);

这不是非常清晰的解决方案，但非常简短。

- sergtk

---

那个解决方案根本不具有普适性。 - twolfe18

Answer 6

这是一个 Ruby 的解决方案。即使对于不熟悉 Ruby 的读者，算法也应该很明显。请注意我如何计算要迭代的行和列（在大多数语言中都会类似地编写）。相比于例如“从max(r-1, 0)到min(r+1, arr.size-1)”来迭代行索引，这对我来说更加简洁。

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

打印

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]

- Cary Swoveland

Answer 7

这是我最近面对类似问题时的解决方案，包括边界检查。我发现它比其他一些建议更易读。你可以将边界检查嵌入循环中，但我认为这种方式更易读。

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

- jtaylor81284

Answer 8

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

输出

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 ]

- Inkollu Akashdhar

---

在C++中输出矩阵中特定位置相邻的位置 - Inkollu Akashdhar