33

有没有一种简单的方法可以在二维数组中找到一个元素的邻居（即一个元素周围的八个元素）？不只是以不同的组合减去和添加到索引，如下所示：

array[i-1][i]
array[i-1][i-1]
array[i][i-1]
array[i+1][i]

... 等等。

4

22 回答 22

42

（伪代码）

row_limit = count(array);
if(row_limit > 0){
  column_limit = count(array[0]);
  for(x = max(0, i-1); x <= min(i+1, row_limit); x++){
    for(y = max(0, j-1); y <= min(j+1, column_limit); y++){
      if(x != i || y != j){
        print array[x][y];
      }
    }
  }
}

当然，这几乎与原始硬编码解决方案一样多行，但是有了这个，您可以尽可能多地扩展“邻居”（2-3 个或更多单元格）

于 2009-03-16T20:53:25.880 回答
22

我认为 Ben 的方法是正确的，尽管我可能会对其进行重新排序，以可能改善局部性。

array[i-1][j-1]
array[i-1][j]
array[i-1][j+1]

array[i][j-1]
array[i][j+1]

array[i+1][j-1]
array[i+1][j]
array[i+1][j+1]

避免边界检查问题的一个技巧是使数组维度比需要的大 2。所以，像这样的小矩阵

3 1 4
1 5 9
2 6 5

实际上实现为

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

然后在求和时，我可以在两个维度上从 1 到 3 下标，并且上面的数组引用保证有效，并且对最终总和没有影响。我假设该示例使用 c 和基于零的下标

于 2009-03-16T22:39:35.687 回答
7

这是来自@seb 原始伪代码的一个有效的 Javascript 示例：

function findingNeighbors(myArray, i, j) {
  var rowLimit = myArray.length-1;
  var columnLimit = myArray[0].length-1;

  for(var x = Math.max(0, i-1); x <= Math.min(i+1, rowLimit); x++) {
    for(var y = Math.max(0, j-1); y <= Math.min(j+1, columnLimit); y++) {
      if(x !== i || y !== j) {
        console.log(myArray[x][y]);
      }
    }
  }
}
于 2013-09-29T05:10:31.680 回答
6

@SebaGR 的替代方案，如果您的语言支持：

var deltas = { {x=-1, y=-1}, {x=0, y=-1}, {x=1, y=-1},
               {x=-1, y=0},               {x=1, y=0},
               {x=-1, y=1},  {x=0, y=1},  {x=1, y=1} };
foreach (var delta in deltas)
{
    if (x+delta.x < 0 || x + delta.x >= array.GetLength(0) ||
        y+delta.y < 0 || y + delta.y >= array.GetLength(1))
        continue;

    Console.WriteLine("{0}", array[x + delta.x, y + delta.y]);
}

如果您可以静态分配增量，则在可读性和可能的​​性能方面略有优势。

于 2009-03-16T21:16:42.530 回答
4

要打印 的邻居L[row][column]：

  print(L[row-1][column-1], L[row-1][column], L[row-1][column+1])
  print(L[row][column-1], L[row][column], L[row][column+1])
  print(L[row+1][column-1], L[row+1][column], L[row+1][column+1])

这可能是最快/最简单的方法就是打印可能的邻居。确保进行索引越界检查。

某些语言可能会提供这样做的捷径，但我不知道。

于 2009-03-16T20:51:50.750 回答
3

这是在 python3+ 中@Seb 的答案的一个实现，它简洁并使用生成器来获得最大性能：

def neighbours(pos, matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows else 0
    for i in range(max(0, pos[0] - 1), min(rows, pos[0] + 2)):
        for j in range(max(0, pos[1] - 1), min(cols, pos[1] + 2)):
            if (i, j) != pos:
                yield matrix[i][j]
于 2018-04-23T05:08:57.577 回答
2

这是 Python 中一个方便的方法：

def neighbors(array,pos):
    n = []
     string = "array[pos.y+%s][pos.x+%s]"
    for i in range(-1,2):
        for j in range(-1,2):
            n.append(eval(string % (i,j)))
    return n

假设 pos 是一些 2D Point 对象，而 array 是一个 2D 数组。

于 2016-07-07T19:35:38.650 回答
1

由于在一个元素周围的矩阵中只有 8 个元素，您可以使用数组来存储不同的索引值。例如，

  int iarr[8] = {-1,-1,-1,0,0,+1,+1,+1};
  int jarr[8] = {-1,0,+1,-1,+1,-1,0,+1};
  for(int i = 0 ; i < 8 ; i++)
   {
    if(arr[x-iarr[i]][y-jarr[i]] == 1)
    {
     //statements
    }
   }  
  /* x and y are the position of elements from where you want to reach out its neighbour */

因为两个数组都只包含 8 个值，所以空间可能不是问题。

于 2017-04-14T06:16:04.243 回答
1

我通常采用的方法在此博客的底部进行了描述： https ://royvanrijn.com/blog/2019/01/longest-path/

我喜欢对 8 个“方向”使用单个整数循环，而不是对方向进行硬编码或使用两个嵌套循环，并使用 (i % 3)-1 和 (i / 3)-1; 请查看带有图像的博客。

它不会嵌套那么深并且易于编写，不需要很多代码！

于 2019-01-07T21:07:08.373 回答
1

网格（矢量 2D 或一维......这里不是问题）
X 和 Y，元素的坐标（或者只是通过参考传递你的矢量元素......）

int neighbour(const Grid & g, const size_t & x, const size_t & y) {
    for (int i = -1; i < 2; ++i)
        for (int j = -1; j < 2; ++j)
            if (x + i >= 0 && x + i < g.row && y + j >= 0 && y + j < g.col)
                //Do some stuff
    return 0;
}
于 2019-05-28T16:37:39.973 回答
1

JS 示例：

    function findingNeighbors(myArray, i, j){
        return myArray.reduce(function(a, b, c){
            if(Math.max(0, i-1) <= c && c <= Math.min(i+1, myArray.length-1)){
                a = a.concat(
                    b.reduce(function(d, e, f){
                    if(f == j && c == i)
                        return d;
                    if(Math.max(0, j-1) <= f && f <= Math.min(j+1, myArray.length-1))
                        d.push(e)
                    return d;
                    },[])
                );
            }
            return a;
        },[]);
    }
于 2019-06-07T22:05:11.763 回答
1 
// My approach in JS

let size = 10
//or some arbitrary number for the size of your grid.

const neighbors = [

[-1, -1], 
[-1, 0], 
[-1, 1], 
[0, -1], 
[0, 1], 
[1, -1], 
[1, 0], 
[1, 1]

]

for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
        neighbors.forEach(([x, y]) => {
            const newI = i + x;
            const newJ = j + y;

            if (
                newI >= 0 && 
                newI < size && 
                newJ >= 0 && 
                newJ < size
               ) {
                // you can access your grid neighbors here ----> grid[newI][newJ];
              }
    ```

I've found this approach helpful because it defines all of the array coordinates as transformations of the existing i and j indexes in your for loops.
于 2020-08-03T03:46:03.233 回答
0

很大程度上取决于您的数据是什么。例如，如果您的二维数组是一个逻辑矩阵，您可以将行转换为整数并使用按位运算来找到您想要的。

对于更通用的解决方案，我认为您会遇到索引问题，例如 SebaGR 的解决方案。

于 2009-03-16T21:11:08.550 回答
0

行和列是行和列的总数

定义一个 CellIndex 结构或类。或者您可以只返回实际值而不是索引。

public List<CellIndex> GetNeighbors(int rowIndex, int colIndex)
{
var rowIndexes = (new int[] { rowIndex - 1, rowIndex, rowIndex + 1 }).Where(n => n >= 0 && n < Rows);

var colIndexes = (new int[] { colIndex - 1, colIndex, colIndex + 1 }).Where(n => n >= 0 && n < Cols);

return (from row in rowIndexes from col in colIndexes where row != rowIndex || col != colIndex select new CellIndex { Row = row, Col = col }).ToList();
}
于 2010-11-24T21:37:17.743 回答
0 
private ArrayList<Element> getNeighbors(Element p) {
    ArrayList<Element> n = new ArrayList<Element>();

    for (int dr = -1; dr <= +1; dr++) {
        for (int dc = -1; dc <= +1; dc++) {
            int r = p.row + dr;
            int c = p.col + dc;

            if ((r >= 0) && (r < ROWS) && (c >= 0) && (c < COLS)) {
                // skip p
                if ((dr != 0) || (dc != 0))
                    n.add(new Element(r, c));
            }               
        }
    }

    return n;
}
于 2014-03-21T19:58:47.377 回答
0

尽管列表推导中的嵌套 for 循环有点难看，但它更短：

def neighbours(m, i, j):
    return [m[x][y] for x in [i-1,i,i+1] for y in [j-1,j,j+1] if x in range(0,len(m)) and y in range(0,len(m[x])) and (x,y) != (i,j)]
于 2016-03-11T07:24:14.130 回答
0

这是 C# 的一些代码：

public Cell[,] MeetNeigbours(Cell[,] Grid)
    {
        for (int X = 0; X < Grid.GetLength(0); X++)
        {
            for (int Y = 0; Y < Grid.GetLength(1); Y++)
            {
                int NeighbourCount = 0;
                for (int i = -1; i < 2; i++)
                {
                    for (int j = -1; j < 2; j++)
                    {
                        if (CellExists(Grid, (X + i)), (Y + j) && (i != 0 && j != 0))
                        {
                            Grid[X, Y].Neighbours[NeighbourCount] = Grid[(X + i), (Y + j)];
                        }
                        if(!(i == 0 && j == 0))
                        {
                            NeighbourCount++;
                        }
                    }
                }
            }
        }
        return Grid;
    }

    public bool CellExists(Cell[,] Grid, int X, int Y)
    {
        bool returnValue = false;
        if (X >= 0 && Y >= 0)
        {
            if (X < Grid.GetLength(0) && Y < Grid.GetLength(1))
            {
                returnValue = true;
            }
        }

        return returnValue;
    }

“Cell”类看起来像这样：

public class Cell
{
    public Cell()
    {
        Neighbours = new Cell[8];
    }

    /// <summary>
    /// 0 3 5
    /// 1 X 6
    /// 2 4 7
    /// </summary>
    public Cell[] Neighbours;
}
于 2016-07-10T22:17:32.327 回答
0

这在最近的一个项目中对我很有帮助，所以这里是 @Seb 的 swift 伪代码实现。这是假设二维数组是正方形的：

func adjacentIndexPaths(to indexPath: IndexPath) -> [IndexPath] {
var neighboringSquareIndexes: [IndexPath] = []

// gridSquareCount is the size of the 2D array. For example, in an 8 x 8 [[Array]], gridSquareCount is 8
let maxIndex = gridSquareCount - 1
var neighborRowIndex = max(0, indexPath.section - 1)
var neighborColumnIndex = max(0, indexPath.row - 1)

while neighborRowIndex <= min(indexPath.section + 1, maxIndex) {
    while neighborColumnIndex <= min(indexPath.row + 1, maxIndex) {
        if neighborRowIndex != indexPath.section || neighborColumnIndex != indexPath.row {
            neighboringSquareIndexes.append(IndexPath(row: neighborColumnIndex, section: neighborRowIndex))
        }
        neighborColumnIndex += 1
    }
    neighborRowIndex += 1
    neighborColumnIndex = max(0, indexPath.row - 1)
}

return neighboringSquareIndexes }
于 2019-02-26T20:02:22.307 回答
0

在 JavaScript 中

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

        function getNeighborsNumbersAtIthJth(i, j) {
            let allPosibleIndexes = [
                [i - 1, j],
                [i, j - 1],
                [i - 1, j - 1],
                [i + 1, j],
                [i, j + 1],
                [i + 1, j + 1],
                [i + 1, j - 1],
                [i - 1, j + 1]
            ];
            let allPosibleValues = []
            allPosibleIndexes.forEach(([i, j]) => {
                try {
                    allPosibleValues.push(arr[i][j])
                } catch (err) {

                }
            })
            return allPosibleValues.filter(v => v != undefined);
        }
        console.log(getNeighborsNumbersAtIthJth(1, 1));//[2, 4, 1, 8, 6, 9, 7, 3]
        console.log(getNeighborsNumbersAtIthJth(0, 1));//[1, 5, 3, 6, 4]
        console.log(getNeighborsNumbersAtIthJth(0, 0));//[4, 2, 5]
于 2020-05-20T18:39:57.833 回答
0

我使用一个方向数组并运行一个循环来获得适当的方向。像这样的东西（代码在 JS 中）

function getAdjacent(matrix, i, j, k) {
  const directions = [
    [i - 1, j - 1],
    [i - 1, j],
    [i - 1, j + 1],
    [i, j - 1],
    [i, j + 1],
    [i + 1, j - 1],
    [i + 1, j],
    [i + 1, j + 1],
  ];
  const [row, col] = directions[k];
  // Check for last rows and columns
  if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[i].length) {
    return undefined;
  }
  return matrix[row][col];
}

function run(){
  const hello = 'hello';
  const matrix = [
    [1, 2, 1],
    [2, 1, 1],
    [1, 1, 1]
  ];

  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      let sum = 0;
      for (let k = 0; k < 8; k++) {
        const res = getAdjacent(matrix, i, j, k);
        console.log(i, j, k, res); // Do whatever you want here
      }
    }
  }
}

run();

于 2020-07-29T00:42:22.467 回答
0

Python 中的这个示例也可能会有所启发：

from itertools import product
def neighbors(coord: tuple, grid=(10, 10), diagonal=True):
    """Retrieve all the neighbors of a coordinate in a fixed 2d grid (boundary).

    :param diagonal: True if you also want the diagonal neighbors, False if not
    :param coord: Tuple with x, y coordinate
    :param grid: the boundary of the grid in layman's terms
    :return: the adjacent coordinates
    """
    width = grid[0] - 1
    height = grid[1] - 1
    retx, rety = coord
    adjacent = []
    nb = [x for x in product([-1, 0, 1], repeat=2) if x != (0, 0)]
    if not diagonal:
        nb = [x for x in nb if x not in product([-1, 1], repeat=2)]
    for x, y in nb:
        xx = retx + x
        yy = rety + y
        if xx < 0 or xx > width or yy < 0 or yy > height:
            # not within its boundaries
            continue
        adjacent.append((xx, yy))
    return adjacent

第一条产品线 ( nb = [x for x in product([-1, 0, 1], repeat=2) if x != (0, 0)]) 将生成其相邻元素的所有坐标，包括对角线坐标。(0,0) 被删除，因为那是我们自己，所以不是邻居:-)

[(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

如果您不想要对角线邻居，您可以告诉它删除那些 ( product([-1, 1], repeat=2))，然后检查网格的边界并生成坐标的结果列表。

于 2021-12-09T17:32:23.633 回答
0

Ruby=> 返回一个邻居数组。

array = [
    [1, 2, 5, 6],
    [8, 89, 44, 0],
    [8, 7, 23, 0],
    [6, 9, 3, 0]
  ]
  
  def neighbours(array, (i , j)) 
    [
      [i, j - 1],
      [i, j + 1],
      [i - 1, j - 1],
      [i - 1, j],
      [i - 1, j + 1],
      [i + 1, j - 1],
      [i + 1, j],
      [i + 1, j + 1],
    ].select { |h, w|
        h.between?(0, array.length - 1) && w.between?(0, array.first.length - 1)
      }.map do |row, col|
          array[row][col]
      end 
  end
  
  array.each_with_index do |row, i|
    row.each_with_index do |col, j|
      p(array[i][j], neighbours(array, [i, j]))
    end 
  end
于 2022-01-31T05:09:31.147 回答