Prenez une région 2D de l'espace divisée en éléments carrés d'unité alignés sur l'axe avec leurs centres alignés à intervalles entiers. Une arête est dite interne si elle est partagée par deux éléments, sinon c'est une arête externe.

Votre objectif est de trouver le nombre minimum d'éléments voisins qui doivent être traversés pour atteindre un bord extérieur à partir du centre de chaque élément, connu sous le nom de traversal distance, ou distancepour faire court. Vous ne pouvez traverser qu'une arête (c.-à-d. Pas de coupure d'angle / mouvement diagonal). Notez que les "éléments extérieurs" (éléments qui ont au moins un bord extérieur) sont considérés comme devant traverser 0des éléments voisins pour atteindre un bord extérieur.

Contribution

L'entrée est une liste de coordonnées de paires entières non négatives indiquant le (x, y) du centre de tous les éléments. On suppose qu'il n'y a pas d'éléments qui se chevauchent (c'est-à-dire qu'une paire x / y identifie de manière unique un élément). Vous ne pouvez rien supposer de l'ordre d'entrée des éléments.

Vous êtes invités à transformer l'origine de l'entrée à n'importe quel endroit (par exemple 0,0 ou 1,1, etc.).

Vous pouvez supposer que tous les éléments d'entrée sont connectés, ou en d'autres termes, il est possible de voyager d'un élément à un autre en utilisant les règles ci-dessus. Notez que cela ne signifie pas que la région 2D est simplement connectée; il peut y avoir des trous à l'intérieur.

Exemple: ce qui suit est une entrée non valide.

0,0
2,0

la vérification des erreurs n'est pas requise.

L'entrée peut provenir de n'importe quelle source (fichier, stdio, paramètre de fonction, etc.)

Production

La sortie doit être une liste de coordonnées identifiant chaque élément et la distance entière correspondante parcourue pour arriver à un bord. La sortie peut être dans n'importe quel ordre d'élément souhaité (par exemple, vous n'avez pas besoin que les éléments de sortie soient dans le même ordre que les entrées).

La sortie peut être vers n'importe quelle source (fichier, stdio, valeur de retour de fonction, etc.)

Toute sortie qui correspond à la coordonnée de l'élément avec sa distance extérieure est très bien, par exemple, tout cela est bien:

x,y: distance
...

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

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

Exemples

Les entrées d'exemple de texte sont sous la forme x,y, avec un élément par ligne; vous êtes invités à remodeler cela dans un format d'entrée pratique (voir les règles de format d'entrée).

Les sorties d'exemple de texte sont au format x,y: distance, avec un élément par ligne; encore une fois, vous êtes invités à remodeler cela dans un format de sortie pratique (voir les règles de format de sortie).

Les figures graphiques ont la limite inférieure gauche comme (0,0), et les nombres à l'intérieur représentent la distance minimale attendue parcourue pour atteindre un bord extérieur. Notez que ces chiffres sont uniquement à des fins de démonstration uniquement; votre programme n'a pas besoin de les afficher.

Exemple 1

contribution:

1,0
3,0
0,1
1,2
1,1
2,1
4,3
3,1
2,2
2,3
3,2
3,3

Production:

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

représentation graphique:

Exemple 2

contribution:

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

production:

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

représentation graphique:

Exemple 3

contribution:

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

production:

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

représentation graphique:

Notation

C'est le golf de code. Le code le plus court en octets gagne. Des échappatoires standard s'appliquent. Toutes les intégrations autres que celles spécifiquement conçues pour résoudre ce problème sont autorisées.

MATLAB / Octave, 143 octets

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

Non golfé

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

Explication

Créez des matrices S ource et R esult de taille appropriée, remplies de zéros.

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

Calculez les indices linéaires qui correspondent aux xypaires, avec un élément de remplissage aux frontières.

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

Dessinez la structure.

S(i)=1;

Sest montré ici pour l' exemple 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

Supprimer tous les éléments de bordure par érosion d'image

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

en utilisant le disque de l' élément structurant de rayon 1 :

0   1   0
1   1   1
0   1   0

Si le mouvement diagonal était autorisé, nous utiliserions plutôt le rectangle:

1   1   1
1   1   1
1   1   1

Ensuite, incrémentez le résultat pour tous les éléments non frontières

R+=S;

et boucle jusqu'à ce que l'image soit complètement érodée.

while nnz(S)

Renvoie le résultat pour chaque xypaire.

v=R(i);

Pyth, 26 octets

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

Exemple 2

Le format de sortie que j'ai utilisé est:

[[4, 3]]
2

C'est-à-dire une liste contenant le point, suivi de la distance de l'extérieur.

Le code fonctionne en utilisant un ensemble actuellement atteint, pour chaque point filtrant l'entrée pour tous les points exactement à une distance de 1 de ce point, et en vérifiant si le nombre de points résultant est 4 fois plus que le nombre de départ, et en répétant jusqu'à ce qu'il ne soit pas . Lorsque démarré à un point donné, cela donne à quelle distance ce point est de l'extérieur.

MATL , 38 37 36 33 octets

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

Cela utilise la version actuelle (15.0.0) du langage / compilateur.

Le format d'entrée est: un tableau avec des valeurs x et un tableau avec des valeurs y . L'entrée et la sortie sont basées sur 1. Les cas de test ont donc les entrées suivantes:

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

Essayez-le en ligne!

Explication

Une matrice est initialement construite avec 1 aux positions d'entrée et 0 sinon. Ensuite, une convolution est appliquée avec un masque "Nord, Est, Sud, Ouest" ([0 1 0; 1 0 1; 0 1 0] ), et le résultat à chaque position est comparé à 4. Un résultat de 4 signifie que cette position est entourée par d'autres points, et donc a distance- vers l'extérieur au moins 1. Le résultat (0 ou 1 pour chaque point) est ajouté à la matrice d'origine. Ces positions contiennent désormais 2 (à la fin du processus, la matrice sera décrémentée de 1).

Le processus de convolution est itéré. Pour l'itération suivante, l'entrée de la convolution est la matrice accumulée seuilée à 2; c'est-à-dire que les valeurs inférieures à 2 sont définies sur 0. Le résultat de la convolution indique quels points ont une distance d'au moins 2 (tous leurs voisins ont la distance 1).

Le nombre d'itérations est choisi, par commodité, comme le nombre de colonnes de la matrice d'entrée. C'est suffisant (en fait, le nombre maximal d'itérations requis est la moitié de la dimension minimale de la matrice). Les dernières itérations peuvent être inutiles, mais ne nuisent pas (elles ajoutent simplement 0 à tous les points).

À la fin du processus, 1 est soustrait du résultat, car les positions de valeur k ont la distance k -1 à l'extérieur. Les coordonnées et les valeurs de toutes les positions sont extraites et affichées.

           % 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 160 octets

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()

On sait que si une coordonnée a moins de quatre voisins, elle doit être à "l'extérieur". Par conséquent, nous pouvons à plusieurs reprises dépouiller les cellules extérieures et leur affecter une distance égale au nombre d'itérations / profondeur de récursivité dans ce cas.

Je pense vraiment qu'il y a place à amélioration - Quelle est la meilleure façon de vérifier les voisins adjacents?

edit: je devrais être autorisé à accepter une liste de paires comme tuples.

PHP, 316 octets

<?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;

Version en ligne

Panne

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

Visualisez en tant que caractères 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";}