Предположим, у нас есть такая матрица:
11111
12221
12321
12221
11111
Эта матрица представляет ландшафт, и каждая ячейка представляет часть ландшафта. Число в каждой ячейке представляет время, в течение которого часть местности должна быть полностью сожжена (в минутах, если требуется единица измерения), в соответствии с ее горючестью . Если пожар начинается в любой заданной позиции (ячейке), эта ячейка должна быть полностью сожжена, прежде чем огонь распространится на соседние ячейки (только по горизонтали и вертикали, а не по диагонали). Итак, если пожар начинается в центральной позиции, огонь должен:
11111 11111 11111 11011 10001 00000
12221 3 m. 12221 2 m. 12021 1 m. 11011 1 m. 00000 1 m. 00000
12321 -----> 12021 -----> 10001 -----> 00000 -----> 00000 -----> 00000
12221 12221 12021 11011 00000 00000
11111 11111 11111 11011 10001 00000
Объяснение:
- Огонь начинается с [2,2] (на основе 0), время горения которого равно 3.
- Через 3 минуты [1,2], [2,1], [2,3], [3,2] начинают гореть.
- Через 2 минуты эти ячейки прекращают гореть, и огонь распространяется на все соседние ячейки, но [0,2], [2,0], [2,4], [0,4] нужно только еще 1 минута, чтобы сгореть, поэтому
- Через 1 минуту эти клетки сжигаются, и эта клетка распространяется на соседние клетки.
- Еще через 1 минуту остальные ячейки, начиная с шага 3, заканчивают гореть, и огонь распространяется на соседние ячейки (которые уже сожжены, поэтому ничего не происходит).
- Через одну последнюю минуту огонь прекращает сжигать всю местность.
Таким образом, решение по этому делу составляет 8 минут. Если пожар начинается в самой верхней левой ячейке [0,0]:
11111 01111 00111 00011 00001 00000
12221 1 12221 1 02221 1 01221 1 00121 1 00011 1
12321 --> 12321 --> 12321 --> 02321 --> 01321 --> 00321 -->
12221 12221 12221 12221 02221 01221
11111 11111 11111 11111 11111 01111
00000 00000 00000 00000 00000
00000 1 00000 1 00000 1 00000 1 00000
00221 --> 00110 --> 00000 --> 00000 --> 00000
00221 00121 00020 00010 00000
00111 00011 00001 00000 00000
Так что теперь общее время составляет 10 минут.
Соревнование
Учитывая NxM матрицу (N> 0, M> 0) целочисленных значений, которые представляют время, когда каждая ячейка должна быть полностью израсходована, напишите самую короткую программу / функцию, которая принимает эту матрицу, и пару целых чисел с позиции, в которой начинается пожар. и возвращает / печатает время, необходимое для пожара, чтобы полностью поглотить всю местность.
- Каждая ячейка будет иметь положительное (ненулевое) время записи. Вы не можете принять максимальное значение для ячеек.
- Матрица не должна быть квадратной или симметричной.
- Матрица может быть 0 или 1, как вам нравится.
- Позиция может быть задана как один параметр с набором целых чисел, двумя отдельными параметрами любого другого приемлемого формата.
- Размеры матрицы не могут быть указаны в качестве входных параметров.
- Вам не нужно выводить каждый промежуточный шаг, просто запрашиваемое количество времени. Но я не буду жаловаться, если шаги визуализируются каким-либо образом.
Другой пример:
Fire starts at [1,1] (a '>' represents a minute):
4253 4253 4253 4153 4043 3033 2023 0001 0000
2213 > 2113 > 2013 > 1003 > 0002 > 0001 > 0000 >> 0000 > 0000
1211 1211 1211 1111 1001 0000 0000 0000 0000
Output: 9
Это код-гольф , поэтому победит самая короткая программа для каждого языка!
источник
1
доM*N
Ответы:
Matlab,
235257190182178 байтВход: матрица
A
, вектор 1x2,p
содержащий начальные координаты.Объяснение:
Вместо того, чтобы моделировать распространение огня, мы также можем понимать это как проблему «найти самый длинный кратчайший путь». Матрица преобразуется в взвешенный ориентированный граф. Весовые коэффициенты путей к одному узлу соответствуют времени записи указанного узла. Например, для матрицы
получаем связный граф:
Где узел 1 - это верхний левый матричный элемент, а узел 12 - нижний правый элемент. Учитывая начальные координаты
p
, вычисляется кратчайший путь ко всем остальным узлам. Тогда длина самого длинного пути из этих самых коротких путей + время для записи начального узла равно времени для записи всей матрицы.Развернутая и прокомментированная версия с примерами начальных значений:
источник
;
после каждой строки. В Matlab это предотвращает отображение результатов каждой команды в консоли. В настоящее время код очень болтливый и спамит консоль. Но так как это не строгое состояние отказа, я сохранил его таким. Но это не имеет большого значения, это всего лишь 4 байтаJavaScript (ES6),
156152146144143 байтаСохранено 1 байт благодаря Кевину Круйссену
Довольно наивная реализация. Принимает ввод в синтаксисе карри
(a)(s)
, где a - это двумерный массив, а s - массив из двух целых чисел [ x, y ], представляющих основанные на 0 координаты начальной позицииОтформатировано и прокомментировано
Контрольные примеры
Показать фрагмент кода
источник
==0
можно в гольф,<1
если я не ошибаюсь.undefined<1
и ложь. Благодарность!Октава, 67 байт
Попробуйте онлайн!
Для визуализации промежуточных результатов вы можете попробовать это!
Функция, которая принимает в качестве входной матрицы ландшафта
a
и начальной координаты матрицу 0 и 1 с тем же размером, что и ландшафт.На самом деле нет необходимости,
endfunction
однако, запускать пример в tio, его следует добавить.Объяснение:
Неоднократно применяйте морфологическое расширение изображения на местности и вычитайте сгоревшие участки из нее.
Беззвучный ответ:
источник
n=1
наn=0
.MATL ,
2625 байтФормат ввода:
Первый вход - это матрица, использующая в
;
качестве разделителя строк.Второй вход - это одно число, которое обращается к элементу матрицы в порядке старших столбцов, основанном на 1 (допускается задачей). Например, главная координата столбца каждой записи в матрице 3 × 4 определяется как
Так, например, основанные на 1 координаты (2,2) соответствуют
5
.Попробуйте онлайн! Или проверьте все тестовые случаи .
объяснение
Код поддерживает список записей, которые горят. На каждой итерации все записи в этом списке уменьшаются. Когда запись достигает нуля, ее соседние записи добавляются в список. Для сохранения байтов записи, которые достигают нуля, не удаляются из списка; вместо этого они продолжают «гореть» с отрицательными значениями. Цикл завершается, когда ни одна из записей не имеет положительных значений.
Посмотрите, как программа работает шаг за шагом со слегка измененным кодом.
Код комментария:
источник
Python 2 , 170 байт
Попробуйте онлайн!
источник
Python 3 ,
277266 байтПопробуйте онлайн!
Определяет функцию,
f
которая принимает 2D-матрицу и кортеж из точек. Первое , что делает функция , это определить набор кортежей , содержащих начальное значение кортежа передается в:p={s}
. Затем функция проходит через каждый набор точекp
и вычитает одну из матрицыm
в этой точке, если только значение уже не равно нулю. Затем онm
снова перебирает все точки с нулевым значением и добавляет четырех соседей этой точки к наборуp
. Вот почему я решил использовать набор, потому что наборы в Python не допускают дублирования значений (что могло бы сильно испортить вычитание). К сожалению, из-за переноса индекса списка (напримерlist[-1] == list[len(list)-1]
:) индексы должны быть ограничены, чтобы они не становились отрицательными и не добавляли неправильные координатыp
.Ничего особенного, все еще привыкаешь к игре в гольф. Определенно, здесь есть место для улучшения, и я буду продолжать это делать.
источник
APL (Dyalog) ,
936657 байтовПопробуйте онлайн! или визуализируй это онлайн!
Эта функция принимает матрицу ландшафта в качестве правого аргумента и координаты (на основе 1) первого огня в качестве левого аргумента. Возвращает количество минут, необходимое для записи всего.
Обновления
Наконец-то нашел способ поиграть в гольф по спреду
* Вздох * было бы намного проще, если бы мир был тороидальным .
TIO только что обновился до Dyalog 16.0 , что означает, что теперь у нас есть новый блестящий оператор трафарета
источник
Python 2 , 268 байт
Попробуйте онлайн!
Рекурсивно повторять шаги по времени, в которых число каждой плитки уменьшается, если она кардинально смежна с 0. Очень простой алгоритм, который, я полагаю, все еще может быть использован для логической эффективности ...
* примечание: мой "Попробуйте онлайн!" код включает в себя бонус отладки журнала в нижнем колонтитуле. Мне нравится наблюдать за прогрессом алгоритма.
источник
Haskell ,
138133 байтаПопробуйте онлайн!
Предполагается, что вход представляет собой список ((x, y), ячейка). Ungolfed:
источник