Qapıların tikintisi#10597
Fermer Con öz fermasının bəzi hissələri ətrafında yeni bir hasar tikmək qərarına gəldi, lakin daim diqqəti yayınır və nəticədə əvvəlcə planlaşdırdığından qat-qat qəribə formalı hasar tikir!
Daha dəqiq desək, Fermer Con nöqtəsindən hərəkətə başlayır və hər dəfə şimala, cənuba, şərqə və ya qərbə bir vahid məsafə keçərək addım atır. Hər addımda o, arxasında bir vahid uzunluğunda hasar parçası çəkir. Məsələn, əgər onun ilk addımı şimala yönəlidirsə, o, nöqtəsindən nöqtəsinə qədər hasar parçası quraşdırır. Fermer Con eyni nöqtələrə dəfələrlə qayıda bilər və hətta eyni hasar parçasını bir neçə dəfə çəkə bilər. Onun hasarı, əgər yolu artıq qurulmuş hasar hissəsindən keçirsə, özünü kəsə bilər.
Təəccüblü deyil ki, hasarın tikintisi başa çatdıqdan sonra Fermer Con nəticədən olduqca narazıdır. Xüsusilə, o, fermanın bəzi hissələrini ayrı-ayrı bölgələrə bölmüş ola biləcəyini görür, belə ki, indi hasarı kəsmədən bir bölgədən digərinə keçmək mümkün deyil. Fermer Con hasara qapılar əlavə etməklə bu problemi həll etmək istəyir. Qapılar onun tikdiyi hasarın istənilən vahid parçasına quraşdırıla bilər, bu isə həmin parçanın iki tərəfi arasında keçidi təmin edir.
Fermer Conun fermasının istənilən hissəsindən istənilən başqa hissəsinə çatmaq imkanını yenidən bərpa etmək üçün quraşdırmalı olduğu minimum qapı sayını təyin edin.
Birinci sətirdə n~(1 \le n \le 1000) tam ədədi verilir. Növbəti sətirdə Fermer Conun marşrutunu təsvir edən uzunluğunda sətir verilir. Hər simvol aşağıdakılardan biridir: (şimal), (şərq), (cənub) və ya (qərb).
Fermerin bütün ferma bölgələri arasında tam əlaqəni bərpa etmək üçün quraşdırmalı olduğu minimum qapı sayını göstərən bir tam ədəd çıxarın. Nəzərə alın ki, əgər ferma əvvəlcədən bağlıdırsa, cavab ola bilər.
Nümunə 1