Ambil wilayah 2D ruang yang dibagi menjadi elemen-elemen unit square yang selaras dengan pusatnya disejajarkan pada interval integer. Tepi dikatakan internal jika dibagikan oleh dua elemen, jika tidak itu adalah tepi eksternal.

Tujuan Anda adalah untuk menemukan jumlah minimum elemen tetangga yang harus dilalui untuk mencapai tepi luar mulai dari pusat setiap elemen, yang dikenal sebagai traversal distance, atau distancesingkatnya. Anda hanya dapat melintasi melalui tepi (yaitu tidak ada pemotongan sudut / gerakan diagonal). Perhatikan bahwa "elemen eksterior" (elemen yang memiliki setidaknya satu tepi eksternal) dianggap perlu melintasi 0elemen tetangga untuk mencapai tepi eksterior ..

Memasukkan

Input adalah daftar koordinat pasangan integer non-negatif yang menunjukkan (x, y) pusat semua elemen. Diasumsikan tidak ada elemen yang tumpang tindih (yaitu pasangan x / y secara unik mengidentifikasi elemen). Anda mungkin tidak menganggap apa pun tentang urutan input elemen.

Anda dapat mengubah asal input ke lokasi mana pun (mis. 0,0 atau 1,1, dll.).

Anda dapat mengasumsikan bahwa semua elemen input terhubung, atau dengan kata lain dimungkinkan untuk melakukan perjalanan dari satu elemen ke elemen lain menggunakan aturan di atas. Perhatikan bahwa ini tidak berarti bahwa wilayah 2D hanya terhubung; mungkin ada lubang di dalamnya.

Contoh: berikut ini adalah input yang tidak valid.

0,0
2,0

pengecekan kesalahan tidak diperlukan.

Input mungkin dari sumber apa pun (file, stdio, parameter fungsi, dll.)

Keluaran

Output harus berupa daftar koordinat yang mengidentifikasi setiap elemen, dan jarak integer yang sesuai dilalui untuk mencapai suatu edge. Output mungkin dalam urutan elemen apa pun yang diinginkan (mis. Anda tidak perlu menampilkan elemen dalam urutan yang sama yang diterima sebagai input).

Outputnya bisa ke sumber mana saja (file, stdio, nilai pengembalian fungsi, dll.)

Output apa pun yang cocok dengan koordinat elemen dengan jarak eksteriornya baik-baik saja, misalnya semua ini baik-baik saja:

x,y: distance
...

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

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

Contohnya

Input contoh teks ada dalam formulir x,y, dengan satu elemen per baris; Anda dipersilakan untuk membentuk kembali ini menjadi format input yang nyaman (lihat aturan format input).

Keluaran contoh teks dalam format x,y: distance, dengan satu elemen per baris; sekali lagi, Anda dapat mengubah bentuk ini menjadi format ouput yang nyaman (lihat aturan format output).

Angka grafis memiliki batas kiri bawah sebagai (0,0), dan angka-angka di dalamnya mewakili jarak minimum yang diharapkan untuk mencapai tepi luar. Perhatikan bahwa angka-angka ini murni untuk tujuan demonstrasi saja; program Anda tidak perlu menampilkan ini.

Contoh 1

memasukkan:

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

Keluaran:

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

representasi grafis:

Contoh 2

memasukkan:

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

keluaran:

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

representasi grafis:

Contoh 3

memasukkan:

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

keluaran:

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

representasi grafis:

Mencetak gol

Ini golf kode. Kode terpendek dalam byte menang. Celah standar berlaku. Setiap bawaan selain dari yang dirancang khusus untuk memecahkan masalah ini diizinkan.

MATLAB / Oktaf, 143 byte

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

Tidak disatukan

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

Penjelasan

Buat S esce dan R esve matriks ukuran yang sesuai, diisi dengan nol.

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

Hitung indeks linier yang sesuai dengan xy-pairs, dengan satu elemen padding di perbatasan.

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

Gambarkan strukturnya.

S(i)=1;

Sditunjukkan di sini untuk Contoh 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

Hapus semua elemen perbatasan oleh erosi gambar

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

menggunakan disk elemen penataan dengan jari-jari 1 :

0   1   0
1   1   1
0   1   0

Jika gerakan diagonal diizinkan, kami menggunakan persegi panjang:

1   1   1
1   1   1
1   1   1

Kemudian, tambahkan hasilnya untuk semua elemen non-perbatasan

R+=S;

dan loop sampai gambar benar-benar terkikis.

while nnz(S)

Kembalikan hasil untuk setiap xy-pair.

v=R(i);

Pyth, 26 byte

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

Contoh 2

Format output yang saya gunakan adalah:

[[4, 3]]
2

Yaitu, daftar yang berisi titik, diikuti oleh jarak dari eksterior.

Kode ini bekerja dengan menggunakan set yang saat ini tercapai, untuk setiap titik memfilter input untuk semua titik tepat jarak 1 dari titik itu, dan memeriksa apakah jumlah poin yang dihasilkan adalah 4 kali lebih banyak dari angka awal, dan ulangi sampai tidak . Ketika dimulai pada titik tertentu, ini memberikan seberapa jauh titik itu dari eksterior.

MATL , 38 37 36 33 byte

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

Ini menggunakan versi saat ini (15.0.0) dari bahasa / kompiler.

Format input adalah: satu array dengan nilai x dan satu array dengan nilai y . Input dan output berbasis 1. Jadi kasus uji memiliki input berikut:

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

Cobalah online!

Penjelasan

Matriks awalnya dibangun dengan 1 pada posisi input dan 0 sebaliknya. Kemudian lilitan diterapkan dengan topeng "Utara, Timur, Selatan, Barat" ([0 1 0; 1 0 1; 0 1 0] ), dan hasil pada setiap posisi dibandingkan dengan 4. Hasil dari 4 berarti bahwa posisi tersebut dikelilingi oleh titik-titik lain, dan juga memiliki jarak- ke-eksterior setidaknya 1. Hasilnya (0 atau 1 untuk setiap titik) ditambahkan ke matriks asli. Posisi-posisi itu sekarang mengandung 2 (pada akhir proses matriks akan dikurangi dengan 1).

Proses konvolusi diulang. Untuk iterasi berikutnya, input konvolusi adalah akumulasi matriks yang di-threshold dengan 2; yaitu, nilai yang lebih rendah dari 2 ditetapkan ke 0. Hasil konvolusi menunjukkan titik mana yang memiliki jarak minimal 2 (semua tetangga mereka memiliki jarak 1).

Jumlah iterasi dipilih, untuk kenyamanan, sebagai jumlah kolom dari matriks input. Ini cukup (pada kenyataannya, jumlah iterasi yang diperlukan maksimum adalah setengah dari dimensi matriks minimum). Iterasi terakhir mungkin tidak berguna, tetapi tidak membahayakan (mereka hanya menambahkan 0 ke semua poin).

Pada akhir proses, 1 dikurangkan dari hasil, karena posisi dengan nilai k memiliki jarak k -1 ke luar. Koordinat dan nilai semua posisi diekstraksi dan ditampilkan.

           % 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 byte

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

Kita tahu bahwa jika koordinat memiliki kurang dari empat tetangga, itu harus berada di "eksterior". Oleh karena itu, kita dapat berulang kali mengupas sel luar dan menetapkan jarak yang sama dengan jumlah iterasi / kedalaman rekursi dalam kasus ini.

Pasti berpikir ada ruang untuk perbaikan - Apa cara terbaik untuk memeriksa tetangga yang berdekatan?

sunting: Saya seharusnya diizinkan menerima daftar pasangan sebagai tupel.

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;

Versi Online

Kerusakan

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

Visualisasikan sebagai karakter 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";}