Weź obszar 2D podzielony na kwadratowe elementy wyrównane do osi z ich środkami wyrównanymi w odstępach całkowitych. Mówi się, że krawędź jest wewnętrzna, jeśli jest współdzielona przez dwa elementy, w przeciwnym razie jest to krawędź zewnętrzna.

Twoim celem jest znalezienie minimalnej liczby sąsiednich elementów, które należy pokonać, aby osiągnąć zewnętrzną krawędź, zaczynając od środka każdego elementu, znanego jako traversal distance, lub distancew skrócie. Możesz przechodzić tylko przez krawędź (tzn. Bez cięcia narożników / ruchu po przekątnej). Uwaga: uważa się, że „elementy zewnętrzne” (elementy, które mają co najmniej jedną krawędź zewnętrzną) muszą przejść przez 0sąsiednie elementy, aby osiągnąć krawędź zewnętrzną.

Wejście

Dane wejściowe to lista nieujemnych współrzędnych pary całkowitych oznaczających (x, y) środka wszystkich elementów. Zakłada się, że nie ma nakładających się elementów (tj. Para x / y jednoznacznie identyfikuje element). Być może nie nic o kolejności wprowadzania elementem zakładać.

Zachęcamy do przekształcenia źródła danych wejściowych w dowolne miejsce (np. 0,0 lub 1,1 itd.).

Możesz założyć, że wszystkie elementy wejściowe są połączone, lub innymi słowy, możliwe jest przejście z jednego elementu do dowolnego innego elementu przy użyciu powyższych reguł. Zauważ, że nie oznacza to, że region 2D jest po prostu połączony; może mieć w środku dziury.

Przykład: poniżej podano nieprawidłowe dane wejściowe.

0,0
2,0

sprawdzanie błędów nie jest wymagane.

Dane wejściowe mogą pochodzić z dowolnego źródła (plik, stdio, parametr funkcji itp.)

Wynik

Dane wyjściowe powinny być listą współrzędnych identyfikujących każdy element i odpowiednią liczbą całkowitą pokonaną, aby dostać się do krawędzi. Dane wyjściowe mogą być w dowolnej pożądanej kolejności elementów (np. Nie trzeba wyjściowych elementów w tej samej kolejności otrzymanej jako dane wejściowe).

Dane wyjściowe mogą pochodzić z dowolnego źródła (plik, stdio, wartość zwracana przez funkcję itp.)

Każde wyjście, które pasuje do współrzędnej elementu z jego odległością zewnętrzną, jest w porządku, np. Wszystkie są w porządku:

x,y: distance
...

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

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

Przykłady

Przykładowe dane tekstowe są w formie x,y, z jednym elementem w wierszu; możesz przekształcić to w wygodny format wejściowy (zobacz zasady dotyczące formatu wejściowego).

Przykładowe wyniki tekstowe są w formacie x,y: distance, z jednym elementem w wierszu; ponownie, możesz przekształcić to w wygodny format wyjściowy (zobacz reguły formatu wyjściowego).

Liczby graficzne mają lewą dolną granicę jako (0,0), a liczby w środku reprezentują oczekiwaną minimalną odległość przebytą do osiągnięcia krawędzi zewnętrznej. Pamiętaj, że liczby te służą wyłącznie do celów demonstracyjnych; twój program nie musi ich wysyłać.

Przykład 1

Wejście:

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

Wynik:

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

Reprezentacja graficzna:

Przykład 2

Wejście:

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

wynik:

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

Reprezentacja graficzna:

Przykład 3

Wejście:

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

wynik:

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

Reprezentacja graficzna:

Punktacja

To jest kod golfowy. Najkrótszy kod w bajtach wygrywa. Obowiązują standardowe luki. Dozwolone są wszelkie wbudowane elementy inne niż specjalnie zaprojektowane w celu rozwiązania tego problemu.

MATLAB / oktawa, 143 bajty

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

Nie golfił

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

Wyjaśnienie

Tworzenie S Ource i R matryc esult o odpowiedniej wielkości, wypełnione zerami.

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

Oblicz indeksy liniowe odpowiadające xyparom, z jednym wypełnieniem elementu na granicach.

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

Narysuj strukturę.

S(i)=1;

Spokazano tutaj dla przykładu 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

Usuń wszystkie elementy obramowania poprzez erozję obrazu

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

za pomocą dysku elementu strukturyzującego o promieniu 1 :

0   1   0
1   1   1
0   1   0

Jeśli dozwolony byłby ruch ukośny, zamiast tego użylibyśmy prostokąta:

1   1   1
1   1   1
1   1   1

Następnie zwiększ wynik dla wszystkich elementów innych niż graniczne

R+=S;

i zapętlaj, aż obraz całkowicie ulegnie erozji.

while nnz(S)

Zwraca wynik dla każdej xypary.

v=R(i);

Pyth, 26 bajtów

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

Przykład 2

Użyłem formatu wyjściowego:

[[4, 3]]
2

To znaczy lista zawierająca punkt, a następnie odległość od zewnętrznej strony.

Kod działa przy użyciu aktualnie osiągniętego zestawu, dla każdego punktu filtrując dane wejściowe dla wszystkich punktów dokładnie w odległości 1 od tego punktu i sprawdzając, czy wynikowa liczba punktów jest 4 razy większa niż liczba początkowa, i powtarzając, aż nie będzie . Kiedy zaczyna się w danym punkcie, pokazuje to, jak daleko ten punkt jest od zewnątrz.

MATL , 38 37 36 33 bajtów

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

Używa bieżącej wersji (15.0.0) języka / kompilatora.

Format wejściowy to: jedna tablica z wartościami x i jedna tablica z wartościami y . Wejścia i wyjścia są oparte na 1. Tak więc przypadki testowe mają następujące dane wejściowe:

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

Wypróbuj online!

Wyjaśnienie

Matryca jest początkowo budowana z 1 w pozycjach wejściowych i 0 w przeciwnym razie. Następnie stosuje się splot z maską „Północ, Wschód, Południe, Zachód” ([0 1 0; 1 0 1; 0 1 0] ), a wynik dla każdej pozycji porównuje się z 4. Wynik 4 oznacza, że ​​pozycja ta jest otoczona innymi punktami, a zatem ma odległość na zewnątrz co najmniej 1. Wynik (0 lub 1 dla każdego punktu) jest dodawany do oryginalnej macierzy. Pozycje te zawierają teraz 2 (pod koniec procesu macierz zostanie zmniejszona o 1).

Proces splotu jest iterowany. Dla następnej iteracji wejściem splotu jest skumulowana macierz progowa z 2; to znaczy wartości mniejsze niż 2 są ustawione na 0. Wynik splotu wskazuje, które punkty mają odległość co najmniej 2 (wszyscy ich sąsiedzi mają odległość 1).

Dla wygody wybiera się liczbę iteracji jako liczbę kolumn macierzy wejściowej. Jest to wystarczające (w rzeczywistości maksymalna wymagana liczba iteracji to połowa minimalnego wymiaru macierzy). Ostatnie iteracje mogą być bezużyteczne, ale nie wyrządzają szkody (po prostu dodają 0 do wszystkich punktów).

Pod koniec procesu 1 jest odejmowane od wyniku, ponieważ pozycje o wartości k mają odległość k -1 od zewnątrz. Współrzędne i wartości wszystkich pozycji zostaną wyodrębnione i wyświetlone.

           % 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 bajtów

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

Wiemy, że jeśli współrzędna ma mniej niż czterech sąsiadów, musi znajdować się „na zewnątrz”. Dlatego możemy wielokrotnie usuwać zewnętrzne komórki i przypisywać im odległość równą liczbie iteracji / głębokości rekurencji w tym przypadku.

Zdecydowanie sądzę, że jest miejsce na ulepszenia - Jaki jest najlepszy sposób sprawdzenia sąsiadujących sąsiadów?

edytuj: Powinienem mieć możliwość zaakceptowania listy par jako krotek.

PHP, 316 bajtów

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

Wersja online

Awaria

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

Wizualizuj jako znaki 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";}