Pegue uma região 2D do espaço dividida em elementos quadrados da unidade alinhada ao eixo, com seus centros alinhados em intervalos inteiros. Uma aresta é considerada interna se for compartilhada por dois elementos, caso contrário, é uma aresta externa.

Seu objetivo é encontrar o número mínimo de elementos vizinhos que devem ser atravessados ​​para alcançar uma borda externa a partir do centro de cada elemento, conhecido como traversal distance, ou distanceabreviado. Você só pode atravessar uma aresta (ou seja, nenhum corte de canto / movimento diagonal). Observe que "elementos externos" (elementos que têm pelo menos uma aresta externa) são considerados necessários para atravessar 0elementos vizinhos para alcançar uma aresta externa.

Entrada

A entrada é uma lista de coordenadas de pares inteiros não negativos que denotam o (x, y) do centro de todos os elementos. Supõe-se que não há elementos sobrepostos (ou seja, um par x / y identifica exclusivamente um elemento). Você não pode assumir nada sobre a ordem de entrada do elemento.

Você pode transformar a origem da entrada em qualquer local (por exemplo, 0,0 ou 1,1, etc.).

Você pode supor que todos os elementos de entrada estejam conectados ou, em outras palavras, é possível passar de um elemento para outro usando as regras acima. Observe que isso não significa que a região 2D esteja simplesmente conectada; pode ter orifícios dentro dele.

Exemplo: a seguir é uma entrada inválida.

0,0
2,0

verificação de erro não é necessária.

A entrada pode ser de qualquer fonte (arquivo, stdio, parâmetro de função, etc.)

Resultado

A saída deve ser uma lista de coordenadas que identificam cada elemento e a distância inteira correspondente percorrida para chegar a uma aresta. A saída pode estar em qualquer ordem de elemento desejada (por exemplo, você não precisa de elementos de saída na mesma ordem que as entradas).

A saída pode ser para qualquer fonte (arquivo, stdio, valor de retorno da função etc.)

Qualquer saída que corresponda à coordenada do elemento com sua distância externa é boa, por exemplo, todas são boas:

x,y: distance
...

[((x,y), distance), ...]

[(x,y,distance), ...]

Exemplos

As entradas de exemplo de texto estão no formulário x,y, com um elemento por linha; você pode remodelá-lo em um formato de entrada conveniente (consulte as regras de formato de entrada).

As saídas de exemplo de texto estão no formato x,y: distance, com um elemento por linha; novamente, você pode remodelá-lo para um formato de saída conveniente (consulte as regras de formato de saída).

As figuras gráficas têm o limite inferior esquerdo como (0,0) e os números dentro representam a distância mínima esperada percorrida para alcançar uma aresta externa. Observe que esses números são apenas para fins de demonstração; seu programa não precisa produzir isso.

Exemplo 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

Resultado:

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

representação gráfica:

Exemplo 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

resultado:

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

representação gráfica:

Exemplo 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

resultado:

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

representação gráfica:

Pontuação

Isso é código de golfe. O código mais curto em bytes vence. Aplicam-se brechas padrão. Quaisquer embutidos que não sejam aqueles projetados especificamente para resolver esse problema são permitidos.

MATLAB / oitava, 143 bytes

function [v,x,y]=d(x,y)R=S=zeros(max(y+3),max(x+3));i=sub2ind(size(S),y+2,x+2);S(i)=1;while nnz(S=imerode(S,strel('disk',1,0)))R+=S;end;v=R(i);

Ungolfed

function [v,x,y]=d(x,y)
  R=S=zeros(max(y+3),max(x+3));
  i=sub2ind(size(S),y+2,x+2);
  S(i)=1;
  while nnz(S=imerode(S,strel('disk',1,0)))
    R+=S;
  end;
  v=R(i);

Explicação

Criar S onte e R matrizes ESULTADO de tamanho apropriado, preenchido com zeros.

R=S=zeros(max(y+3),max(x+3));

Calcule os índices lineares que correspondem aos xypares, com um elemento preenchendo nas bordas.

i=sub2ind(size(S),y+2,x+2);

Desenhe a estrutura.

S(i)=1;

Sé mostrado aqui para o Exemplo 2 :

0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   1   0   0   0   0   0
0   0   1   0   1   1   1   1   0   0   0
0   1   1   1   1   1   1   1   1   0   0
0   0   1   1   1   1   1   1   1   1   0
0   0   0   1   1   1   1   1   0   0   0
0   0   0   0   1   1   1   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0

Remova todos os elementos da borda por erosão da imagem

S=imerode(S,strel('disk',1,0))

usando o disco do elemento estruturador com raio 1 :

0   1   0
1   1   1
0   1   0

Se o movimento diagonal fosse permitido, usaríamos o retângulo:

1   1   1
1   1   1
1   1   1

Em seguida, incremente o resultado para todos os elementos que não sejam de borda

R+=S;

e faça um loop até que a imagem seja completamente erodida.

while nnz(S)

Retorne o resultado para cada xypar.

v=R(i);

Pitão, 26 bytes

V]MQNf>*4Nl=Nsmfq1.a,dYQN0

Exemplo 2

O formato de saída que usei é:

[[4, 3]]
2

Ou seja, uma lista contendo o ponto, seguido pela distância do exterior.

O código funciona usando um conjunto alcançado no momento, para cada ponto que filtra a entrada de todos os pontos a uma distância exata 1 desse ponto e verifica se o número de pontos resultante é 4 vezes maior que o número inicial e se repete até que não seja . Quando iniciado em um determinado ponto, isso mostra a que distância esse ponto está do exterior.

MATL , 38 37 36 33 bytes

1Z?t"tX@<~5Bt!Z~2X53$Y+4=+]3#fqhh

Isso usa a versão atual (15.0.0) do idioma / compilador.

O formato de entrada é: uma matriz com valores x e uma matriz com valores y . Entrada e saída são baseadas em 1. Portanto, os casos de teste têm as seguintes entradas:

[2 4 1 2 2 3 5 4 3 3 4 4]
[1 1 2 3 2 2 4 2 3 4 3 4]

[5 2 4 5 6 7 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 3 4 5 6 7 4 5 6]
[1 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 6 6 6]

[5 5 2 4 5 6 7 9 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 3 4 5 6 7 10 11 12 4 5 6 10 11 12 7 8 9 10 11 12]
[1 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 8]

Experimente online!

Explicação

Uma matriz é inicialmente construída com 1 nas posições de entrada e 0 no caso contrário. Em seguida, uma convolução é aplicada com uma máscara "Norte, Leste, Sul, Oeste" ( [0 1 0; 1 0 1; 0 1 0]), e o resultado em cada posição é comparado com 4. Um resultado de 4 significa que essa posição é cercada por outros pontos e, portanto, tem distância- para exterior pelo menos 1. O resultado (0 ou 1 para cada ponto) é adicionado à matriz original. Essas posições agora contêm 2 (no final do processo, a matriz será decrementada por 1).

O processo de convolução é iterado. Para a próxima iteração, a entrada da convolução é a matriz acumulada com limiar com 2; ou seja, valores menores que 2 são definidos como 0. O resultado da convolução indica quais pontos têm distância pelo menos 2 (todos os seus vizinhos têm distância 1).

O número de iterações é escolhido, por conveniência, como o número de colunas da matriz de entrada. Isso é suficiente (na verdade, o número máximo necessário de iterações é metade da dimensão mínima da matriz). As últimas iterações podem ser inúteis, mas não causam danos (elas simplesmente adicionam 0 a todos os pontos).

No final do processo, 1 é subtraído do resultado, porque as posições com valor k têm distância k -1 ao exterior. As coordenadas e os valores de todas as posições são extraídos e exibidos.

           % take x and y implicitly
1          % push 1
Z?         % build sparse matrix from that x, y indices with 1 as value
t          % duplicate
"          % for each column of that matrix
  t        %   duplicate
  X@       %   push iteration index
  <~       %   true for matrix entries that are >= iteration index
  5B       %   5 in binary: row vector [1 0 1]
  t!       %   duplicate and transpose into a column vector
  Z~       %   element-wise XOR with broadcast: gives desired mask,
           %   [0 1 0; 1 0 1; 0 1 0]
  2X53$Y+  %   2D convolution. Output has same size as input
  4=       %   compare with 4: are all neighbouring positions occupied?
  +        %   add to accumulated matrix from previous iteration
]          % end for each
3#f        % extract row index, column index and value for nonzero
           % entries. In this case all entries are nonzero
q          % subtract 1 to value to yield distance to exterior
hh         % concatenate vertically twice
           % display implicitly 

Python 3, 180 166 160 bytes

def f(l,d=0):
 l=set(l);
 if l:i={(a,b)for a,b in l if all([x in l for x in[(a+1,b),(a-1,b),(a,b+1),(a,b-1)]])};return{(c,d)for c in l-i}|f(i,d+1)
 return set()

Sabemos que se uma coordenada tem menos de quatro vizinhos, ela deve estar no "exterior". Portanto, podemos retirar repetidamente as células externas e atribuir a elas uma distância igual ao número de iterações / profundidade de recursão nesse caso.

Definitivamente acho que há espaço para melhorias - Qual é a melhor maneira de verificar vizinhos vizinhos?

editar: devo ter permissão para aceitar uma lista de pares como tuplas.

PHP, 316 bytes

<?preg_match_all("#^(\d+),(\d+)#m",$_GET[i],$t);foreach($t[1]as$k=>$v)$a[$v][$t[2][$k]]=0;function w($x,$y){global$a;return isset($a[$x][$y])?$a[$x][$y]:-1;};for(;$z++<max($t[2]);$o=$s,$s="")foreach($a as$x=>$b)foreach($b as$y=>$c)$s.="\n$x,$y: ".$a[$x][$y]=1+min(w($x+1,$y),w($x-1,$y),w($x,$y-1),w($x,$y+1));echo$o;

Versão Online

Demolir

preg_match_all("#^(\d+),(\d+)#m",$_GET[i],$t); 
foreach($t[1]as$k=>$v) 
$a[$v][$t[2][$k]]=0;  # make a 2 D array
function w($x,$y){global$a;return isset($a[$x][$y])?$a[$x][$y]:-1;};# check the neighbours
for(;$z++<max($t[2]);$o=$s,$s="") # stored the last loop string first run make possible to 1 and so on
foreach($a as$x=>$b) # x values
foreach($b as$y=>$c) # y values
$s.="\n$x,$y: ".$a[$x][$y]=1+min(w($x+1,$y),w($x-1,$y),w($x,$y-1),w($x,$y+1)); # concanate array item x+y+value
echo$o; #Output

Visualize como caracteres Ascii

ksort($a); 
foreach($a as$x=>$b){
for($y=0;$y<=max($t[2]);$y++)
echo isset($a[$x][$y])?$a[$x][$y]:" ";
#The better way would be make a SVG and use the text element and use a factor
#echo '<text x="'.($x*$factor).'" y="'.($y*$factor).'">'.$a[$x][$y].'</text>';
echo"\n";}