Так как завтра 4 мая, вот небольшой пост на тему «Звездных войн», чтобы мысленно подготовить вас ко всем плохим шуткам, которые появятся завтра.

предыстория

Во время сессии галактического сената все сенаторы сидят в n*nсетке. Внезапная вспышка гриппа JarJar (которая длится вечно и заставляет зараженных говорить как JarJar Binks) вызывает заражение некоторых сенаторов.

Вот пример с 6*6сеткой, где Xзараженные сенаторы, соответствующий список [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]:

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

Мы можем заключить, что сенатор может быть соседним с 2,3 или 4 другими сенаторами и требовать следующие правила заражения:

• Зараженный сенатор остается зараженным навсегда
• Сенатор заражается на шаге, если он был рядом с 2 или более зараженными сенатором на предыдущем шаге

Вот пример с предыдущей сеткой, которая показывает 2 первых шага заражения:

После следующих шагов весь сенат будет заражен

ТВОЕ ЗАДАНИЕ

Ваш код не должен обрабатывать неверные данные, такие как список больше n*nили координаты, которые не являются отличительными.

Ваш код будет принимать в качестве входных данных список пар целых чисел (или двоичной сетки или любого другого формата, который подходит вашему языку) и целое число n(которое может быть ненужным, если вы используете другой формат, чем список), например:

8 [[1,2],[1,1],[7,4],[2,7],[4,3]]

n является стороной сетки, что означает, что сетка будет * n сеткой, а список пар целых чисел будет координатами ячеек изначально зараженных сенаторов.

Нижний левый угол сетки [0,0], а верхний правый - [n-1, n-1]. Слева вверху - [0, n-1].

Ваш код должен вывести целое число:

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

Контрольные примеры

6 [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]] => 7

4 [[1,1][0,3][1,0][3,0][3,3]] => 9

Помните, что это код-гольф , поэтому выигрывает самый короткий ответ в байтах!

MATL, 29 28 байт

tn:"tlY6Z+1>Z|t?@.]]Nl=?l_]&

Ввод в виде двумерной матрицы 1 и 0

Попробуйте это на MATL Online

объяснение

        % Implicitly grab user input as a 2D matrix
t       % Duplicate the inputs
n:      % Count the number of elements in the input (N) and create the array [1...N]
"       % Loop this many times (maximum number of steps we analyze)
  t     % Duplicate the top element
  lY6   % Push the 2D array => [0 1 0; 1 0 1; 0 1 0]
  Z+    % Perform 2D convolution (and maintain the size)
  l>    % Find all values that are >= 2
  Z|    % Perform an element-wise OR with the previous state
  t?    % If all elements are 1's
    @.  % Push the current index and break out of the loop
  ]     % End of if 
]       % End of for loop
Nl=?    % If there is only one element on the stack
  l_    % Push a negative one
]       % End of if statement
&       % Display the top stack element

APL (Dyalog 16.0), 54 символа или 60 байтов

Принимает вложенную матрицу в качестве аргумента, возвращает номер шага, который завершает заражение, т.е. 1 = уже полностью заражен. 0 = не распространяется полностью, это всего лишь 1 + номера ОП.

54 символа (Unicode):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

60 байтов (классический):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⎕U233A 3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

⌺ эквивалентно ⎕U233A

Примеры запуска:

      g←(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵ ⋄ (⊂f⊃⍵),⍵}⍣≡
      ⎕IO←0
      b←⊂⊖⍉~@(⎕JSON'[[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]]')⊢0⍴⍨2⍴6
      g b
8
      b←⊂⊖⍉~@(⎕JSON'[[1,1],[0,3],[1,0],[3,0],[3,3]]')⊢0⍴⍨2⍴4
      g b
10

Шаги следующие:

┌─────────────┬─────────────┬─────────────┬─────── ──────┬─────────────┬─────────────┬─────────────┬─ ────────────┐
│ XX │ XXX │ XXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXXX │
│ X │ XXX │ XXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXXX │ XXXXXX │
│ XX │ XXX │ XXXX │ XXXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ │ X │ XXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ X │ XX │ XXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ XX │ XXXX │ XXXX │ XXXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
└─────────────┴─────────────┴─────────────┴─────── ──────┴─────────────┴─────────────┴─────────────┴─ ────────────┘
┌─────────┬─────────┬─────────┬─────────┬───────── ┬─────────┬─────────┬─────────┬─────────┬───────── ┐
│ XX │ XX │ XX │ XX │ XX │ XX │ XXX │ XXXX │ XXXX │ XXXX │
│ │ │ │ │ X │ XX │ XXX │ XXXX │ XXXX │ XXXX │
│ X │ X │ XX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXXX │ XXXX │
│ XX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXXX │
└─────────┴─────────┴─────────┴─────────┴───────── ┴─────────┴─────────┴─────────┴─────────┴───────── ┘

Pyth , 49 байтов

J^UE2*lK.uS{+NeMf>hT1r8S@Jsmm+VdkNs_MB_MBU2Q)qJeK

Тестовый пакет .

Использует 1-индексирование для вывода.

Python, 231 байт

g=input()
q=lambda r,c:g[r][c]if(0<=r<m)*(0<=c<m)else 0
m=len(g);p=t=0;n=range(m)
while not all([r for k in g for r in k]):h=[[g[r][c]or sum([q(r+1,c),q(r-1,c),q(r,c+1),q(r,c-1)])>1 for c in n] for r in n];t+=1;0/(g!=h);g=h
print t

Возникает ошибка, если это невозможно.

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

JavaScript (ES6), 132 байта

f=s=>(w=s.search`\n`,t=` `.repeat(w+1),t+=s+t,t=s.replace(/0/g,(_,i)=>1-t[i]-t[i+=w]-t[i+=2]-t[i+w]>>>31),t==s?0/!/0/.test(s):1+f(t))

Где \nпредставляет буквальный символ новой строки. Принимает ввод в виде строки 0s и 1s в массиве с разделителями новой строки. Возвращает, NaNесли сетка никогда не станет полностью зараженной.