Tome una región 2D del espacio dividida en elementos cuadrados unitarios alineados con ejes con sus centros alineados a intervalos enteros. Se dice que un borde es interno si es compartido por dos elementos, de lo contrario es un borde externo.
Su objetivo es encontrar el número mínimo de elementos vecinos que deben atravesarse para alcanzar un borde exterior comenzando desde el centro de cada elemento, conocido como traversal distance
, o distance
para abreviar. Solo puede atravesar un borde (es decir, sin corte de esquina / movimiento diagonal). Tenga en cuenta que se considera que los "elementos exteriores" (elementos que tienen al menos un borde externo) deben atravesar 0
elementos vecinos para alcanzar un borde exterior.
Entrada
La entrada es una lista de coordenadas de pares enteros no negativos que denotan el (x, y) del centro de todos los elementos. Se supone que no hay elementos superpuestos (es decir, un par x / y identifica de forma exclusiva un elemento). Es posible que no asumir nada sobre el orden de entrada de elemento.
Puede transformar el origen de la entrada en cualquier ubicación (por ejemplo, 0,0 o 1,1, etc.).
Puede suponer que todos los elementos de entrada están conectados, o en otras palabras, es posible viajar de un elemento a otro utilizando las reglas anteriores. Tenga en cuenta que esto no significa que la región 2D simplemente esté conectada; Puede tener agujeros en su interior.
Ejemplo: lo siguiente es una entrada no válida.
0,0
2,0
no se requiere verificación de errores.
La entrada puede ser de cualquier fuente (archivo, stdio, parámetro de función, etc.)
Salida
La salida debe ser una lista de coordenadas que identifiquen cada elemento, y la distancia entera correspondiente recorrida para llegar a un borde. La salida puede estar en cualquier orden de elementos deseado (por ejemplo, no necesita elementos de salida en el mismo orden recibido como entradas).
La salida puede ser a cualquier fuente (archivo, stdio, valor de retorno de función, etc.)
Cualquier salida que coincida con la coordenada del elemento con su distancia exterior está bien, por ejemplo, todos estos están bien:
x,y: distance
...
[((x,y), distance), ...]
[(x,y,distance), ...]
Ejemplos
Las entradas de ejemplo de texto tienen el formato x,y
, con un elemento por línea; puede reformar esto en un formato de entrada conveniente (consulte las reglas de formato de entrada).
Las salidas de ejemplo de texto están en formato x,y: distance
, con un elemento por línea; de nuevo, puede reconfigurar esto en un formato de salida conveniente (vea las reglas de formato de salida).
Las figuras gráficas tienen el límite inferior izquierdo como (0,0), y los números en el interior representan la distancia mínima esperada recorrida para alcanzar un borde exterior. Tenga en cuenta que estas cifras son solo para fines de demostración; su programa no necesita generar estos.
Ejemplo 1
entrada:
1,0
3,0
0,1
1,2
1,1
2,1
4,3
3,1
2,2
2,3
3,2
3,3
Salida:
1,0: 0
3,0: 0
0,1: 0
1,2: 0
1,1: 1
2,1: 0
4,3: 0
3,1: 0
2,2: 1
2,3: 0
3,2: 0
3,3: 0
representación grafica:
Ejemplo 2
entrada:
4,0
1,1
3,1
4,1
5,1
6,1
0,2
1,2
2,2
3,2
4,2
5,2
6,2
7,2
1,3
2,3
3,3
4,3
5,3
6,3
7,3
8,3
2,4
3,4
4,4
5,4
6,4
3,5
4,5
5,5
salida:
4,0: 0
1,1: 0
3,1: 0
4,1: 1
5,1: 0
6,1: 0
0,2: 0
1,2: 1
2,2: 0
3,2: 1
4,2: 2
5,2: 1
6,2: 1
7,2: 0
1,3: 0
2,3: 1
3,3: 2
4,3: 2
5,3: 2
6,3: 1
7,3: 0
8,3: 0
2,4: 0
3,4: 1
4,4: 1
5,4: 1
6,4: 0
3,5: 0
4,5: 0
5,5: 0
representación grafica:
Ejemplo 3
entrada:
4,0
4,1
1,2
3,2
4,2
5,2
6,2
8,2
0,3
1,3
2,3
3,3
4,3
5,3
6,3
7,3
8,3
9,3
1,4
2,4
3,4
4,4
5,4
6,4
7,4
8,4
9,4
2,5
3,5
4,5
5,5
6,5
9,5
10,5
11,5
3,6
4,6
5,6
9,6
10,6
11,6
6,7
7,7
8,7
9,7
10,7
11,7
salida:
4,0: 0
4,1: 0
1,2: 0
3,2: 0
4,2: 1
5,2: 0
6,2: 0
8,2: 0
0,3: 0
1,3: 1
2,3: 0
3,3: 1
4,3: 2
5,3: 1
6,3: 1
7,3: 0
8,3: 1
9,3: 0
1,4: 0
2,4: 1
3,4: 2
4,4: 2
5,4: 2
6,4: 1
7,4: 0
8,4: 0
9,4: 0
2,5: 0
3,5: 1
4,5: 1
5,5: 1
6,5: 0
9,5: 0
10,5: 0
11,5: 0
3,6: 0
4,6: 0
5,6: 0
9,6: 0
10,6: 1
11,6: 0
6,7: 0
7,7: 0
8,7: 0
9,7: 0
10,7: 0
11,7: 0
representación grafica:
Puntuación
Este es el código de golf. El código más corto en bytes gana. Se aplican lagunas estándar. Se permiten todos los elementos integrados que no sean los diseñados específicamente para resolver este problema.
Respuestas:
MATLAB / Octave, 143 bytes
Sin golf
Explicación
Crear S ource y R matrices ESULTADO de tamaño apropiado, llena con ceros.
Calcule los índices lineales que corresponden a los
xy
pares, con un elemento de relleno en los bordes.Dibuja la estructura.
S
se muestra aquí para el Ejemplo 2 :Eliminar todos los elementos de borde por erosión de imagen
utilizando el disco del elemento estructurante con radio 1 :
Si se permitiera el movimiento diagonal, en su lugar usaríamos el rectángulo:
Luego, incremente el resultado para todos los elementos no fronterizos
y bucle hasta que la imagen esté completamente erosionada.
Devuelve el resultado para cada
xy
par.fuente
Pyth, 26 bytes
Ejemplo 2
El formato de salida que utilicé es:
Es decir, una lista que contiene el punto, seguido de la distancia desde el exterior.
El código funciona utilizando un conjunto alcanzado actualmente, para cada punto que filtra la entrada para todos los puntos exactamente a una distancia de ese punto, y verifica si el número resultante de puntos es 4 veces mayor que el número inicial, y repite hasta que no sea . Cuando se inicia en un punto dado, esto da qué tan lejos está ese punto del exterior.
fuente
MATL ,
38373633 bytesEsto usa la versión actual (15.0.0) del lenguaje / compilador.
El formato de entrada es: una matriz con valores xy una matriz con valores y . La entrada y la salida están basadas en 1. Entonces los casos de prueba tienen las siguientes entradas:
Pruébalo en línea!
Explicación
Una matriz se construye inicialmente con 1 en las posiciones de entrada y 0 en caso contrario. Luego, se aplica una convolución con una máscara "Norte, Este, Sur, Oeste" (
[0 1 0; 1 0 1; 0 1 0]
), y el resultado en cada posición se compara con 4. Un resultado de 4 significa que esa posición está rodeada por otros puntos, y por lo tanto tiene distancia- al exterior al menos 1. El resultado (0 o 1 para cada punto) se agrega a la matriz original. Esas posiciones ahora contienen 2 (al final del proceso, la matriz se reducirá en 1).El proceso de convolución se repite. Para la siguiente iteración, la entrada de la convolución es la matriz acumulada trillada con 2; es decir, los valores inferiores a 2 se establecen en 0. El resultado de la convolución indica qué puntos tienen una distancia de al menos 2 (todos sus vecinos tienen una distancia de 1).
El número de iteraciones se elige, por conveniencia, como el número de columnas de la matriz de entrada. Esto es suficiente (de hecho, el número máximo requerido de iteraciones es la mitad de la dimensión mínima de la matriz). Las últimas iteraciones pueden ser inútiles, pero no causan daño (simplemente agregan 0 a todos los puntos).
Al final del proceso, 1 se resta del resultado, porque las posiciones con valor k tienen una distancia k -1 al exterior. Se extraen y se muestran las coordenadas y los valores de todas las posiciones.
fuente
Python 3,
180166160 bytesSabemos que si una coordenada tiene menos de cuatro vecinos, debe estar en el "exterior". Por lo tanto, podemos eliminar repetidamente las celdas exteriores y asignarles una distancia igual al número de iteraciones / profundidad de recursión en este caso.
Definitivamente creo que hay margen de mejora: ¿cuál es la mejor manera de verificar a los vecinos adyacentes?
editar: se me debería permitir aceptar una lista de pares como tuplas.
fuente
PHP, 316 bytes
Versión en línea
Descompostura
Visualizar como caracteres Ascii
fuente