eolymp
bolt
Try our new interface for solving problems
Məsələlər

Постройка ворот

Постройка ворот

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Фермер Джон строит изгородь.

ФД начинает в позиции (0, 0) и делает n шагов, двигаясь каждый раз на Единицу расстояния на север, юг, восток или запад. Каждый раз, когда он делает шаг, он строит изгородь за собой. Например, если первый его шаг будет на север, он добавит сегмент изгороди от (0, 0) до (0, 1). ФД может посещать точки повторно много раз и даже может строить одни и те же отрезки изгороди много раз. Его изгородь может даже пересекать себя много раз.

ФД в результате может разделить изгородями ферму на несколько независимых огороженных участков. Он хочет добавить двери для исправления такого положения. Дверь может быть установлена на любом отрезке единичной длины, так чтобы разрешить проход между двумя сторонами этого отрезка.

Определите минимальное количество дверей которые требуется построить, так чтобы каждый регион был доступен из каждого другого региона.

Giriş verilənləri

Первая строка содержит n (1n1000). Следующая строка содержит строку длины n, описывающую путь ФД. Каждый символ один из N (север), E (восток), S (юг), W (запад).

Çıxış verilənləri

Выведите минимальное количество ворот, которое должен построить ФД, чтобы восстановить полную связность всех регионов своей фермы. Заметим, что ответ может быть 0, если ферма изначально связная.

Nümunə

Giriş verilənləri #1
14
NNNESWWWSSEEEE
Çıxış verilənləri #1
2
Mənbə 2016 USACO Январь, Серебро