Encontrar celda de cuadrícula no vacía en matriz bidimensional

Question

Tengo una matriz de enteros bidimensional (digamos 1000 por 1000), llamémosla matriz. Cada celda de esta matriz tiene una coordenada X e Y (cada una de 0 a 999 en este ejemplo). Inicialmente todas las celdas de la grilla tienen un valor de 0. Durante el tiempo de ejecución del programa, algunas de las celdas de la matriz están configuradas en otro valor <> 0.

Ahora necesito una función rápida (algoritmo) que tome algunos valores X e Y y devuelve el valor de la matriz en esas coordenadas. Sin embargo, si la matriz en la ubicación X/Y especificada es 0, entonces el algoritmo debe determinar un valor distinto de cero dentro de la matriz que sea lo más cercano posible a la ubicación X/Y original.

He pensado en un bucle alrededor de la posición original de X/Y con el incremento del desplazamiento en cada ciclo del bucle, pero no estoy seguro de si esto es realmente el algoritmo más rápido ...

¿Alguna idea? Preferiría el código de Java, pero cualquier pseudo-código también está bien :)

¡Gracias de antemano por su ayuda! Saludos cordiales, Matthias

Answer 1

Si la matriz es relativamente escasa y el número de pruebas es alto en relación con el número de insertos, el enfoque ingenuo podría llevar mucho tiempo.

La alternativa es construir un árbol de partición espacial como un árbol quadtree o k-d. La búsqueda del vecino más cercano es O (ln N) a costa de O (ln N) tiempos de inserción.

Answer 2

Si no tiene ninguna suposición sobre cómo se ve la matriz, debe usar el método de fuerza bruta para ver todos los valores cerca de la posición [X, Y].

1. acaba de establecer cuadrado de 3x3 con la posición [X, Y] en el centro y poner a prueba todos los valores en la plaza del perímetro
2. si no encuentra el valor que no sea cero, simplemente continuar con 5x5 cuadrados, 7x7, etc., hasta que encuentres algo. Debes manejar el borde de la gran matriz.

Es solo un trabajo con ciclos, índices y ifs correctos :-) No hay algoritmo más rápido, porque no tiene ninguna información, guía.

Answer 3

Depende de la cantidad de líneas/columnas que espere que contengan valores distintos de 0. Si espera que la cuadrícula de 1000x1000 tenga < 100 ubicaciones ocupadas, debe almacenar la información de la fila & que no es 0 mientras genera los valores.

Si eso no es una opción Usar algo como esto:

public void foo() { 
    int[][]matrix = new int[1000][1000]; 
    int x = 0,y = 0; 
    if(matrix[x][y] != 0) return; 
    int min = 0, max=0; 
    boolean cont = true; 
    foreverloop: 
    while(cont) { 
     min--;max++; 
     for(int ii = min; ii < max; ii++) { 
      // secure that min and max dont exeed matrix here. 
      cont = false; 
      int[] higherEnd = Arrays.copyOf(matrix[ii], max); 
      int[] trunk = Arrays.copyOf(higherEnd, higherEnd.length-min); 
      Arrays.sort(trunk); 
      if(trunk[trunk.length-1] != 0) { 
       // HIT! we search this distance but no further. 
       trunk = Arrays.copyOf(higherEnd, higherEnd.length-min); 
       int source = trunk.length; 
       for(int distance = 0; ;distance++) { 
        if(source-distance>0) { 
         if(trunk[source-distance] != 0) { 
          // SCORE! 
          scoreHit(x+ii,y+source-distance); 
          break foreverloop; 
         } 
        } 
        if(source+distance<trunk.length) { 
         if(trunk[source+distance] != 0) { 
          // SCORE! 
          scoreHit(x+ii,y+source-distance); 
          break foreverloop; 
         } 
        } 
       } 
      } 
     } 
    } 
} 

public void scoreHit(int x, int y) { 
    // there could be several in nearly the same distances 
} 

que podría optimizar esa filtrando las áreas que ya buscado, pero creo que haría una diferencia sólo a distancias mayores de x, y