¿Obtienes elementos adyacentes en una matriz bidimensional?

Question

I tienen una matriz de dos dimensiones, dicen

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 para 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 

Thanks!

Answer 1

Si no está preocupado por el orden, el 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 itere sobre eso en su lugar.

Como se señaló en los comentarios, es probable que desee agregar controles de límites. Se podría hacer eso como esto (suponiendo 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]); 
     } 
    } 
} 

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 solución no es muy clara, pero muy corto.

Answer 3

que probablemente iría 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}}; 

entonces sería iterar sobre las direcciones usando un bucle simple:

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]) en lugar del 8 anterior.

Answer 4

personalmente, los bucles son más feos que el original.

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 qué desea que los valores de - lo que se hace en las diferentes direcciones implica si desea que los valores de las variables o no separados.

Para el procesamiento de estilo de juego de la vida, normalmente quiere trabajar en un patrón de bits en lugar de una matriz de valores individuales, y puede escanear horizontalmente inspeccionando solamente tres de las ocho celdas a la vez usando acumuladores y temporales. Para las convoluciones de gráficos, use una biblioteca existente con un núcleo de 3x3.

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

Answer 5

Aquí hay una solución de Ruby. El algoritmo debería ser evidente incluso para lectores que no están familiarizados con Ruby.

def adjacent(arr, r, c) 
    last_row, last_col = arr.size-1, arr.first.size-1 
    ([r-1,0].max..[r+1,last_row].min).each_with_object([]) do |i, a| 
    ([c-1,0].max..[c+1,last_col].min).each { |j| a << arr[i][j] unless i==r && j==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| 
    (1..3).each do |j| 
    puts "adjacent to #{arr[i][j]} at r=#{i}, c=#{j} = #{adjacent(arr, i, j)}" 
    end 
end 

impresiones

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