UniLecs #120_1. Линия Фронта
UniLecsЗадача: на карте боевых действий есть прямоугольный участок, где идут самые ожесточенные бои. Прямоугольник задан символьной матрицей. Элемент матрицы обозначает территорию 1х1, ктр захвачена либо армией 'R', либо 'F'. Необходимо определить линию фронта в условных единицах, а также общий периметр каждой из сторон.
Входные данные: area[] - символьная матрица, состоящая из символов 'R' и 'F'. Размер матрицы NxM, где N, M - от 1 до 1000.
Захваченные территории каждой из сторон это связные области.
Вывод: линия фронта, общие периметры каждой из сторон.
Пример:
area = [ { 'R', 'R' }, { 'R', 'F' } ]
Answer: FrontLine = 2; PerimeterR = 8; PerimeterF = 4
Реализация:
- @pakrulin, JS: 1.5 балла
https://jsbin.com/wefixiteqo/edit?js,console
2. @jinxonik, Python: 1.5 балла + 1.5 балла за 3 доп.варианта решения = 3 балла
Алгоритмы 1 и 2 весьма простые и быстрые, основаны на переборе всех ячеек с проверкой соседних. Остальные два основаны на алгоритмах заливки областей. Во алгоритмах 3 и 4 делается 2 прохода, по одному для каждой армии. Подробный разбор смотрите в gist-файле
https://gist.github.com/jin-x/07dee78898a66a29787370992f71b1a5
Test:
https://repl.it/@jin_x/UniLecs-120-BattleFrontpy
3. @lPestl, С++, F#: 1.5 балла + 0.5 за второй метод решения + 0.1 за доп.реализацию на другом языке + 0.5 за визуализацию + 0.2 балла за шикарные комментарии в реализации на F# = 2.8 балла
Подробный разбор смотрите в gist-файлах
C++
https://gist.github.com/lpestl/096426373cc195a8bdbef6b6db859582
F#
https://gist.github.com/lpestl/c8a39e52f4a23a7b274c40460b0dbcd5
4. @egormasharskii, C++: 2 балла за 2 варианта решения
Можно заметить, что если линия фронта пересекает поле от грани до грани то ее длина вполне может быть линейной. Во всяком случае в предыдущем решении мы просматривали точки которые однозначно не могли нас заинтересовать (внутренние точки областей). Было бы хорошо если алгоритм старался следовать границе между областями и просматривал бы только точки на линии фронта или точки принадлежащие только периметру. Собственно мы сдесь это и делаем. Начинаем с точки (0,0) т.к она точно нас интересует (принадлежит периметру) и используя очередь "интересных вершин" вдоль периметра и линии фронта. Тут есть один вырожденный случай. Это когда одна область полностью лежит внутри другой ("котел","бублик"). Очевидно что в таком случае алгоритм не найдет линию фронта. В этом случае приходится в массиве найти первую точку принадлежащию противнику и повторить алгоритм в этой точке (эта точка будет граничной). После чего результаты скомпоновать.
https://gist.github.com/myegor/b1d24738aedaadb45abb05e1e58f2c23
Test:
5. Volodymyr, С: 1 балл
https://gist.github.com/f0rget/2d9edd3ee4614387b1678dfc8a76e3d6
6. @dbond762, Go: 1.5 балла
Смотрим для каждого поля его соседа справа и слева. Если они разные - то между ними линия фронта. Также смотрим все крайние поля карты и прибавляем к периметру той стороны, которая держит поле. После к периметрам обеих сторон добавляем линию фронта.
https://gist.github.com/dbond762/0c339883116d1c40c2a72dec3e846bd0
Test:
https://play.golang.org/p/MsVaKEI4YqI
7. @akolosov364, JS: 1.5 балла + 1 балл за Шикарную визуализацию = 2 балла
Смысл задачи заключается в простом проходе по матрице и проверке соседних клеток, если клетка является граничной, по одной из линий периметр увеличивается на 1. Линия фронта увеличивается на 1 если клетка снизу или справа является клеткой вражеской фракции.
https://gist.github.com/KolosovAO/b7329921b24310b8e0918c0c9a741e82
Шикарная Визуализация решения:
8. @FutorioFranklin, Python: 1 балл
Проверяются соседи элемента target, если права(или и снизу) стоит противник,прибавляется единица к периметру и периметру противника, так же прибавляется единица к линии фронта, если стоит союзник, то ничего не прибавлять. Так же нужно учитывать углы и стенки.
https://gist.github.com/futorio/f48cbde6ce22914b4182ecaf6721628e
9. Антон, Rust: 1.5 балла за решение общего случая для несвязных областей.
https://gist.github.com/AnthonyMikh/0865af31248894129b4b70f0b3f22650
Test:
https://play.rust-lang.org/?gist=01a72e99719264cc767a369e527fb1af
10. @Loskir, JS: 1.5 балла
https://gist.github.com/Loskir/216eabb4d87f7d7b2cc21c9eefd35147
Test:
https://repl.it/@Loskir/GrossVapidUtility
11. @tvolf, PHP: 1.5 балла
Для подсчета длин периметров и фронтовой линии используем классический поиск/обход в ширину. Выбираем свободные точки на карте и далее обходим связанные области, подсчитывая значения длины фронтовой линии и периметров.
https://gist.github.com/tvolf/42968222eb14d7bbcf71dde8fda406ea
12. @kirillmotrichkin, Python: 2 балла за два варианта решения.
Два решения - брут-форс и умный обход перимерта: умный обход не работает в особых случаях, тогда вызываем брут-форс на большой матрице умный обход в 5 раз быстрее, на малых может быть до 2 раз медленнее брут-форса. Обходим периметр первой попавшейся стороны по правилу правой руки не сработает, если противник находится на острове и не касается стенок (тогда вызовем брут-форс)брут-форс: заходим в каждую ячейку и смотрим, с кем она граничит отдельно считаем внешний периметр.
https://gist.github.com/superkiria/6ac257ef4f9d0b7365d31b1b9547c13c
Test:
https://repl.it/@superkiria/unilecs120front
13. @Zernov_A, Java: 1.5 балла
Перебираем все элементы матрицы и для каждого расматриваем 4-х соседей. Если соседние элементы разные - то между ними линия фронта. В данном алгоритме в расчете длинны линии фронта и периметра, линия фронта учитывается дважды. Поэтому после всех расчетов необходимо из периметра вычесть "задвоенную линию фронта".
https://github.com/AlexZDeveloper/FrontLine
Test:
https://repl.it/@AlexZDeveloper/FrontLine
14. @LostInKadath, С++: 1 балл
I've just finished my two weeks vacation, so I'm a slowpoke now and need some time to return to work.So... bruteforce O(N*M) is all I'm capable of right now. =)
Роман, держитесь! :)
https://gist.github.com/LostInKadath/3159da8d8ff2d30364b3078e47dfe6bb
15. @voodoo_woodpecker, Python: 1.5 балла
Подробный разбор смотрите в gist файле!
https://gist.github.com/MikePeleah/bd6d6dbe61a2df3b0e69344a69a10bdf
Test: