UniLecs #120. Линия Фронта
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
Идея: работаем с 2х мерным массивом:
- найдем линию фронта;
- параллельно будем рассматривать крайние стороны символьной матрицы (правая, левая, верхняя и нижняя сторона матрицы) для определения внешнего периметра каждой из сторон.
Для определению линии фронта рассмотрим элемент area[i,j]:
- смотрим по строке: если элемент различается с area[i + 1, j], то между ними есть линия фронта;
- смотрим по столбцу: если элемент различается с area[i, j + 1], то между ними также есть линия фронта.
Рассмотрим пример:
| 'R', 'R' |
| 'R', 'F' |
Линия фронта = 2 единицы
Периметр R = 2 (сверху) + 1 (снизу) + 2 (слева) + 1 (справа) + 2 (Линия фронта) = 8 единиц
Периметр F = 1 (снизу) + 1 (справа) + 2 (Линия Фронта) = 4 единицы
Реализация:
https://gist.github.com/unilecs/3b127016940dafa8d17f4ee723c00323
Test: