Нахождение соседей в двумерном массиве

Question

Есть ли простой способ найти соседей (то есть восемь элементов вокруг элемента) элемента в двумерном массиве? Если не считать простого вычитания и добавления в индекс в различных комбинациях, например:

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

... и т. Д.

Answer 1

(псевдо-код)

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 или более ячеек)

Answer 2

Я думаю, что Бен прав в своем подходе, хотя я мог бы изменить его, чтобы возможно улучшить местность.

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 и нулевые индексы для примера

Answer 3

Вот рабочий пример Javascript из исходного псевдокода @seb:

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

Answer 4

альтернатива @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]);
}

Небольшое преимущество в удобочитаемости, возможной производительности, если вы можете статически распределять дельты.

Answer 5

array[i][j] имеет соседей

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

Вероятно, это самый быстрый / простой способ - просто перечислить всех возможных соседей. Удостоверьтесь, чтобы сделать индекс вне проверки границ, хотя.

Некоторые языки могут предложить кратчайший способ сделать это, но я не знаю ни одного.

Answer 6

Это реализация ответа @ Seb в python3 +, которая является краткой и использует генераторы для максимальной производительности:

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]

Answer 7

Вот удобный метод в 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, а массив - это 2D массив.

Answer 8

Сетка (вектор 2D или одно измерение ... здесь не проблема)
X & Y, координата вашего элемента (или просто передайте ваш векторный элемент по ref ...)

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

Answer 9

Это было очень полезно для меня в недавнем проекте, так что вот реализация псевдокода @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 }

Answer 10

Подход, который я обычно использую, описан внизу этого блога: https://royvanrijn.com/blog/2019/01/longest-path/

Вместо жесткого кодирования направлений или наличия двух вложенных циклов я хотел бы использовать один целочисленный цикл для 8 «направлений» и использовать (i% 3) -1 и (i / 3) -1; Изучите блог с изображениями.

Он не такой глубокий и легко написан, не нужно много кода!