Есть ли простой способ найти соседей (т.е. восемь элементов вокруг элемента) элемента в двумерном массиве? Если вы не просто вычитаете и добавляете индекс в разные комбинации, например:
array[i-1][i]
array[i-1][i-1]
array[i][i-1]
array[i+1][i]
... И так далее.
(псевдокод)
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 или более ячеек)
Я думаю, что Бен прав в своем подходе, хотя я могу изменить его порядок, чтобы улучшить местность.
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 и индексы на основе нуля для примера
альтернатива @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]);
}
Небольшое преимущество в удобочитаемости, возможная производительность, если вы можете статически распределять дельта.
Вот рабочий пример 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]);
}
}
}
}
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]
Вероятно, самый быстрый/простой способ - просто перечислить всех возможных соседей. Не забудьте сделать индекс из связанной проверки.
Некоторые языки могут предложить ярлык для этого, но я ничего не знаю.
Вот удобный метод в 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, а массив является двумерным массивом.
Это реализация ответа @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]
Многое зависит от ваших данных. Например, если ваш 2D-массив является логической матрицей, вы можете преобразовать строки в целые числа и использовать побитовые операции для поиска тех, которые вы хотите.
Для более универсального решения, я думаю, вы застряли в индексировании, например, в решении SebaGR.
Строки и столбцы - это общее количество строк и столбцов
Определите структуру или класс 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();
}
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;
}
хотя вложенные для циклов в списках понимаются немного уродливыми, это короче:
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)]
вот какой код для С#:
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;
}
Так как в матрице вокруг элемента есть только 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 значений, тогда пространство может не быть проблемой.
Подход, который я обычно использую, описан внизу этого блога: https://royvanrijn.com/blog/2019/01/longest-path/
Вместо того, чтобы жестко кодировать направления или иметь два вложенных цикла, я хотел бы использовать один целочисленный цикл для 8 'направлений и использовать (i% 3) -1 и (i/3) -1; проверить блог с изображениями.
Он не так глубоко и легко написан, не нужно много кода!
Это было очень полезно для меня в недавнем проекте, так что здесь реализация псевдокода @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 }
Сетка (вектор 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;
}
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;
},[]);
}