Задача №112681. Извилистый путь
Блуждать по поверхности Плюка, не имея никаких ориентиров - занятие не из приятных. Очень часто земляне, случайно оказавшись там, бродили неделями, не находя ни одной живой души.
Пролетая над одной из плюканских пустынь, Би заметил, что она вся изрезана линией чьих-то следов. Землянин, оставивший их, двигался весьма своеобразно: во-первых, все его движения были параллельны осям "север-юг" и "запад-восток". Во-вторых, он совершал одинаковые переходы длиной 1 километр каждый день. Траектория его движения представляла собой замкнутую ломаную, которая могла пересекать сама себя, но никогда не проходила дважды по одному и тому же отрезку.
Би заметил, что в пустыне есть участки, со всех сторон ограниченные траекторией движения человека. Когда-то от Уэфа он слышал, что достаточно четырех цветов для раскраски географической карты так, чтобы никакие два участка, имеющие общую сторону, не имели одного цвета. Би задался вопросом: а каково минимальное число цветов, которое достаточно, чтобы покрасить участки внутри замкнутой ломаной, представляющей собой путь несчастного заблудившегося землянина? Повторяем, что как и на географической карте, соприкасающиеся участки должны иметь разный цвет.
На первой строке входного файла - целое число \(N\) (4 ≤ \(N\) ≤ 100000) - число переходов, сделанное километров. Во второй строке описание траектории движения человека. Это строка из \(N\) символов из набора "N", "E", "S", "W", означающих соответственно движение на север, восток, юг и запад. Гарантируется, что если из начальной точки совершить переходы в направлениях в заданном порядке, то траектория получится замкнутой и без самоналожений (возможно, с самопересечениями).
Выведите целое число от 1 до 4 - минимальное количество цветов, в которые можно покрасить ограниченные траекторией участки так, чтобы никакие две области, имеющие общую сторону, не имели один цвет.
4 NWSE
1