Nehmen Sie einen 2D-Raumbereich, der in achsenausgerichtete quadratische Einheiten unterteilt ist, deren Zentren in ganzzahligen Intervallen ausgerichtet sind. Eine Kante wird als intern bezeichnet, wenn sie von zwei Elementen gemeinsam genutzt wird, andernfalls handelt es sich um eine externe Kante.

Ihr Ziel ist es, die minimale Anzahl benachbarter Elemente zu finden, die durchlaufen werden müssen, um eine Außenkante zu erreichen, die von der Mitte jedes Elements ausgeht, die als traversal distanceoder distancekurz als bezeichnet wird. Sie dürfen nur eine Kante durchfahren (dh kein Eckenschneiden / Diagonalbewegung). Es ist zu beachten, dass "äußere Elemente" (Elemente mit mindestens einer äußeren Kante) 0benachbarte Elemente überqueren müssen , um eine äußere Kante zu erreichen.

Eingang

Die Eingabe ist eine Liste nicht negativer ganzzahliger Paarkoordinaten, die die (x, y) der Mitte aller Elemente angeben. Es wird angenommen, dass es keine überlappenden Elemente gibt (dh ein x / y-Paar identifiziert ein Element eindeutig). Sie können nicht alles über das Element Eingabereihenfolge übernehmen.

Sie können den Ursprung der Eingabe an einen beliebigen Ort verschieben (z. B. 0,0 oder 1,1 usw.).

Sie können davon ausgehen, dass alle Eingabeelemente verbunden sind, oder mit anderen Worten, es ist möglich, mit Hilfe der obigen Regeln von einem Element zu einem anderen Element zu gelangen. Beachten Sie, dass dies nicht bedeutet, dass die 2D-Region einfach verbunden ist. es kann Löcher in sich haben.

Beispiel: Die folgende Eingabe ist ungültig.

0,0
2,0

Fehlerprüfung ist nicht erforderlich.

Die Eingabe kann aus einer beliebigen Quelle stammen (Datei, STDIO, Funktionsparameter usw.).

Ausgabe

Die Ausgabe sollte eine Liste von Koordinaten sein, die jedes Element identifizieren, und der entsprechende ganzzahlige Abstand, der durchlaufen wird, um zu einer Kante zu gelangen. Die Ausgabe kann in jeder gewünschten Elementreihenfolge erfolgen (z. B. müssen Sie die Elemente nicht in derselben Reihenfolge ausgeben, in der sie als Eingaben empfangen wurden).

Die Ausgabe kann an eine beliebige Quelle erfolgen (Datei, STDIO, Funktionsrückgabewert usw.).

Jede Ausgabe, die die Koordinate des Elements mit seiner Außenentfernung übereinstimmt, ist in Ordnung, z.

x,y: distance
...

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

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

Beispiele

Beispieltexteingaben erfolgen in der Form x,ymit einem Element pro Zeile. Sie können dies gerne in ein bequemes Eingabeformat umformen (siehe Regeln für das Eingabeformat).

Textbeispielausgaben sind im Format x,y: distancemit einem Element pro Zeile. Sie können dies auch gerne in ein bequemes Ausgabeformat umformen (siehe Regeln für das Ausgabeformat).

Bei grafischen Figuren ist die linke untere Grenze (0,0), und die Zahlen im Inneren geben die erwartete Mindeststrecke an, die zurückgelegt werden muss, um eine Außenkante zu erreichen. Beachten Sie, dass diese Zahlen nur zu Demonstrationszwecken dienen. Ihr Programm muss diese nicht ausgeben.

Beispiel 1

Eingang:

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

Ausgabe:

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

grafische Darstellung:

Beispiel 2

Eingang:

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

Ausgabe:

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

grafische Darstellung:

Beispiel 3

Eingang:

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

Ausgabe:

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

grafische Darstellung:

Wertung

Das ist Code Golf. Kürzester Code in Bytes gewinnt. Es gelten Standardlücken. Alle anderen als die speziell zur Lösung dieses Problems entwickelten integrierten Funktionen sind zulässig.

MATLAB / Octave, 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);

Erläuterung

Erstellen S ource und R eiter Matrizen geeigneter Größe, gefüllt mit Nullen.

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

Berechnen Sie die linearen Indizes, die den xyPaaren entsprechen, wobei ein Element an den Rändern aufgefüllt wird.

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

Zeichnen Sie die Struktur.

S(i)=1;

Swird hier für Beispiel 2 gezeigt :

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

Entfernen Sie alle Randelemente durch Bilderosion

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

mit der Strukturierungselementscheibe mit Radius 1 :

0   1   0
1   1   1
0   1   0

Wenn diagonale Bewegung erlaubt wäre, würden wir stattdessen das Rechteck verwenden:

1   1   1
1   1   1
1   1   1

Erhöhen Sie dann das Ergebnis für alle nicht umrandeten Elemente

R+=S;

und Schleife, bis das Bild vollständig erodiert ist.

while nnz(S)

xyGibt das Ergebnis für jedes Paar zurück.

v=R(i);

Pyth, 26 Bytes

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

Beispiel 2

Das von mir verwendete Ausgabeformat ist:

[[4, 3]]
2

Das heißt, eine Liste mit dem Punkt, gefolgt von der Entfernung vom Äußeren.

Der Code verwendet eine aktuell erreichte Menge, filtert für jeden Punkt die Eingabe für alle Punkte, die genau 1 von diesem Punkt entfernt sind, und überprüft, ob die resultierende Anzahl von Punkten viermal so hoch ist wie die Startnummer . Wenn an einem bestimmten Punkt begonnen wird, gibt dies an, wie weit dieser Punkt vom Äußeren entfernt ist.

MATL , 38 37 36 33 Bytes

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

Dies verwendet die aktuelle Version (15.0.0) der Sprache / des Compilers.

Das Eingabeformat ist: ein Array mit x- Werten und ein Array mit y- Werten. Eingang und Ausgang sind 1-basiert. Die Testfälle haben also folgende Eingaben:

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

Probieren Sie es online!

Erläuterung

Zunächst wird eine Matrix mit 1 an den Eingabepositionen und 0 ansonsten erstellt. Dann wird eine Faltung mit einer Maske "Nord, Ost, Süd, West" ( [0 1 0; 1 0 1; 0 1 0]) angewendet und das Ergebnis an jeder Position mit 4 verglichen. Ein Ergebnis von 4 bedeutet, dass diese Position von anderen Punkten umgeben ist und somit mindestens 1 nach außen. Das Ergebnis (0 oder 1 für jeden Punkt) wird zur ursprünglichen Matrix hinzugefügt. Diese Positionen enthalten jetzt 2 (am Ende des Prozesses wird die Matrix um 1 dekrementiert).

Der Faltungsprozess wird iteriert. Für die nächste Iteration ist die Eingabe der Faltung die akkumulierte Matrix, die mit 2 begrenzt ist; Das heißt, Werte unter 2 werden auf 0 gesetzt. Das Ergebnis der Faltung gibt an, welche Punkte mindestens 2 entfernt sind (alle ihre Nachbarn haben Abstand 1).

Die Anzahl der Iterationen wird der Einfachheit halber als Anzahl der Spalten der Eingabematrix gewählt. Dies ist ausreichend (tatsächlich ist die maximal erforderliche Anzahl von Iterationen die Hälfte der minimalen Matrixdimension). Die letzten Iterationen mögen nutzlos sein, schaden aber nicht (sie addieren einfach 0 zu allen Punkten).

Am Ende des Prozesses wird 1 vom Ergebnis abgezogen, da Positionen mit dem Wert k einen Abstand k -1 nach außen haben. Die Koordinaten und Werte aller Positionen werden extrahiert und angezeigt.

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

Wir wissen, dass sich eine Koordinate, die weniger als vier Nachbarn hat, auf der "Außenseite" befinden muss. Daher können wir die äußeren Zellen wiederholt entfernen und ihnen einen Abstand zuweisen, der in diesem Fall der Anzahl der Iterationen / der Tiefe der Rekursion entspricht.

Denken Sie auf jeden Fall, es gibt Raum für Verbesserungen. Wie lassen sich benachbarte Nachbarn am besten überprüfen?

edit: Ich sollte eine Liste von Paaren als Tupel akzeptieren dürfen.

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;

Online Version

Nervenzusammenbruch

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

Visualisieren Sie als ASCII-Zeichen

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";}