Плюс жизни под землёй в том, что вам не надо покупать жильё по высоким ценам, ведь вы можете вырыть себе квартиру сами! Как раз этим и занят домашний питомец Ануара — крот Кртек. Он начинает с одной свободной квадратной клетки. Затем он выбирает одно из четырёх направлений, расчищает, если нужно, соседнюю клетку в этом направлении и перемещается туда. Какое максимальное количество дверей сможет поставить крот Кртек так, чтобы из любой точки полученного жилища он мог попасть в любую другую, не пройдя ни через одну дверь?
Строка из не более, чем 1000 символов 'N', 'E', 'S', 'W', описывающая маршрут Кртека.
Ответ — максимальное количество дверей.
NNNWSSSWNNN
6
NNWWSSEE
1
Двери ставить можно только на границе двух смежных жилых клеток. Один из вариантов расстановки дверей в первом примере:
