algorithm - operaciones - arreglos unidimensionales

¿Obtener elementos adyacentes en una matriz bidimensional?

Question

Tengo una matriz bidimensional, digamos

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

Y necesito obtener todos los números adyacentes a 1 (2, 3, 4, 5, 6, 7, 8, 9)

¿Hay una solución menos fea que:

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

¡Gracias!

Answer 1

Aquí hay una solución de rubí. El algoritmo debe ser evidente incluso para los lectores que no están familiarizados con Ruby. Observe cómo he calculado las filas y columnas sobre las que se va a iterar (que se escribirían de manera similar en la mayoría de los idiomas). Esto me parece mucho más limpio que, por ejemplo, "de max(r-1, 0) a min(r+1, arr.size-1) " para los índices de las filas a iterar.

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

huellas dactilares

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]

Answer 2

En C++ esto puede verse como:

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

Esta no es una solución muy clara pero muy corta.

Answer 3

Personalmente, los bucles son más feos que los originales.

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 ]

Pero sin especificar para qué desea los valores, lo que hace en las diferentes direcciones implica si quiere los valores en variables separadas o no.

Para el procesamiento del estilo de juego de la vida, normalmente desea trabajar en un patrón de bits de todos modos en lugar de en una serie de valores individuales, y puede escanear horizontalmente inspeccionando solo tres de las ocho celdas a la vez con acumuladores y temporarios. Para las convoluciones de gráficos, use una biblioteca existente con un kernel de 3x3.

La otra forma de tratar los límites es expandir la matriz en una celda en cada dirección. Esto evita ramas caras en el código de convolución.

Answer 4

Probablemente buscaría una lista constante de dx, dy para cada dirección, así:

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

Luego, recorres las instrucciones con un simple bucle:

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

Por supuesto, puede usar sizeof(directions) / sizeof(directions[1]) lugar de las 8 anteriores.

Answer 5

Si no está preocupado por el pedido, lo más limpio es probablemente usar un par de bucles:

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

Si el orden es importante, puede construir una lista de todos los (dx, dy) en el orden que desee e iterar sobre eso.

Como se señaló en los comentarios, es probable que desee agregar controles de límites. Podrías hacer eso así (asumiendo que el orden no importa):

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