Возьмите двухмерную область пространства, разделенную на выровненные по оси единичные квадратные элементы с центрами, выровненными через целые интервалы. Ребро называется внутренним, если оно совместно используется двумя элементами, в противном случае это внешнее ребро.

Ваша цель - найти минимальное количество соседних элементов, которые необходимо пройти, чтобы достичь внешнего ребра, начиная с центра каждого элемента, известного как traversal distance, или distanceдля краткости. Вы можете проходить только через край (то есть без углового резания / диагонального перемещения). Обратите внимание, что «внешние элементы» (элементы, которые имеют по крайней мере один внешний край), как полагают, должны пройти через 0соседние элементы, чтобы достичь внешнего края.

вход

Входные данные представляют собой список неотрицательных целочисленных парных координат, обозначающих (x, y) центра всех элементов. Предполагается, что нет перекрывающихся элементов (т. Е. Пара x / y однозначно идентифицирует элемент). Вы не можете предполагать что-либо о порядке ввода элементов.

Вы можете преобразовать источник ввода в любое место (например, 0,0 или 1,1 и т. Д.).

Вы можете предположить, что все входные элементы связаны, или, другими словами, возможно перейти от любого одного элемента к любому другому элементу, используя правила выше. Обратите внимание, что это не означает, что 2D-область просто связана; в нем могут быть отверстия.

Пример: ниже приведен неверный ввод.

0,0
2,0

проверка ошибок не требуется.

Ввод может быть из любого источника (файл, stdio, параметр функции и т. Д.)

Выход

Выходными данными должен быть список координат, идентифицирующих каждый элемент, и соответствующее целочисленное расстояние, пройденное для достижения края. Вывод может быть в любом порядке элементов (например, вам не нужно выводить элементы в том же порядке, что и входные данные).

Вывод может быть любым источником (файл, stdio, возвращаемое значение функции и т. Д.)

Любые выходные данные, которые соответствуют координате элемента с его внешним расстоянием, хороши, например, все это хорошо:

x,y: distance
...

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

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

Примеры

Текстовые примеры ввода находятся в форме x,y, с одним элементом на строку; Вы можете изменить это в удобный формат ввода (см. правила формата ввода).

Текстовые примеры выводятся в формате x,y: distanceс одним элементом на строку; опять же, вы можете изменить это в удобный формат вывода (см. правила формата вывода).

Графические фигуры имеют нижнюю левую границу как (0,0), а числа внутри представляют ожидаемое минимальное расстояние, пройденное для достижения внешнего края. Обратите внимание, что эти цифры предназначены только для демонстрационных целей; ваша программа не должна выводить их.

Пример 1

вход:

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

Выход:

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

графическое представление:

Пример 2

вход:

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

выход:

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

графическое представление:

Пример 3

вход:

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

выход:

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

графическое представление:

счет

Это код гольф. Самый короткий код в байтах побеждает. Применяются стандартные лазейки. Разрешены любые встроенные модули, кроме специально разработанных для решения этой проблемы.

MATLAB / Octave, 143 байта

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

объяснение

Создать S Ource и R esult матрицу соответствующего размера, наполненный нули.

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

Вычислить линейные индексы, которые соответствуют xy-парам, с заполнением одним элементом на границах.

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

Нарисуйте структуру.

S(i)=1;

Sпоказано здесь для примера 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

Удалить все граничные элементы путем эрозии изображения

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

с помощью структурирующего элемента диска с радиусом 1 :

0   1   0
1   1   1
0   1   0

Если бы диагональное движение было разрешено, мы бы вместо этого использовали прямоугольник:

1   1   1
1   1   1
1   1   1

Затем увеличьте результат для всех элементов без границ

R+=S;

и цикл, пока изображение не будет полностью размыто.

while nnz(S)

Вернуть результат для каждой xyпары.

v=R(i);

Pyth, 26 байт

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

Пример 2

Формат вывода, который я использовал:

[[4, 3]]
2

То есть список, содержащий точку, за которой следует расстояние от внешней стороны.

Код работает с использованием набора, достигнутого в данный момент, для каждой точки, отфильтровывая входные данные для всех точек на точном расстоянии 1 от этой точки, и проверяя, равно ли полученное число точек в 4 раза, чем начальное число, и повторяя до тех пор, пока это не произойдет. , Когда начинается в данной точке, это дает, как далеко эта точка от внешней.

MATL , 38 37 36 33 байта

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

При этом используется текущая версия (15.0.0) языка / компилятора.

Формат ввода: один массив со значениями x и один массив со значениями y . Вход и выход основаны на 1. Таким образом, тестовые случаи имеют следующие входные данные:

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

Попробуйте онлайн!

объяснение

Матрица изначально строится с 1 на входных позициях и 0 в противном случае. Затем применяется свертка с маской "Север, Восток, Юг, Запад" ([0 1 0; 1 0 1; 0 1 0] ), и результат в каждой позиции сравнивается с 4. Результат 4 означает, что эта позиция окружена другими точками, и поэтому имеет расстояние - to-external как минимум 1. Результат (0 или 1 для каждой точки) добавляется к исходной матрице. Эти позиции теперь содержат 2 (в конце процесса матрица будет уменьшена на 1).

Процесс свертки повторяется. Для следующей итерации входной сигнал свертки представляет собой накопленную матрицу с порогом 2; то есть значения ниже 2 устанавливаются в 0. Результат свертки показывает, какие точки имеют расстояние не менее 2 (все их соседи имеют расстояние 1).

Количество итераций для удобства выбрано в качестве количества столбцов входной матрицы. Этого достаточно (на самом деле максимальное требуемое количество итераций составляет половину минимального размера матрицы). Последние итерации могут быть бесполезными, но не причиняют вреда (они просто добавляют 0 ко всем точкам).

В конце процесса 1 вычитается из результата, потому что позиции со значением k имеют расстояние k -1 до внешней стороны. Координаты и значения всех позиций извлекаются и отображаются.

           % 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 байт

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

Мы знаем, что если у координаты меньше четырех соседей, она должна быть на «внешности». Поэтому мы можем многократно обрезать внешние ячейки и назначить им расстояние, равное количеству итераций / глубине рекурсии в этом случае.

Определенно подумайте, есть ли место для улучшений. Какой лучший способ проверки соседних соседей?

редактировать: мне нужно разрешить принимать список пар в качестве кортежей.

PHP, 316 байт

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

Онлайн версия

Сломать

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

Визуализируйте как символы 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";}