Göleti Təmir Et#6600
Bir karides ferması, verilmiş bir tam ədəd N üçün 2N sıra və 2N+1 sütunlu kvadrat hüceyrələrdən ibarət bir ızgara şəklində tikilmiş düzbucaqlı bir hovuzdan istifadə edir. Hər hüceyrənin tərəfi bir metr uzunluğundadır. Hovuzda dəqiq olaraq (2N-1)×N uzunluğu iki metr olan baryerlər var, müxtəlif növ karideslərin yetişdirilməsi üçün hovuzun içərisində kiçik bölmələri müvəqqəti olaraq təcrid etmək üçün istifadə olunur. Baryerlərin orta nöqtələri dəqiq olaraq tam ədədi koordinatlarda (a, b) sabitlənmişdir, burada 0 < a < 2N və 0 < b < 2N+1, həm a, həm də b təkdir və ya hər ikisi cütdür. Hər baryer hovuzun konfiqurasiyasını dəyişdirmək üçün orta nöqtəsi ətrafında fırlana bilər; lakin fırlanaraq, baryer yalnız iki mümkün mövqedən birinə keçə bilər, həmişə hovuz tərəflərinə paralel, şaquli və ya üfüqi. Aşağıdakı şəkildə sol tərəfdə N = 3 olan bir hovuz konfiqurasiyası göstərilir.
Hər mövsümün sonunda hovuz təmir və təmizləmə üçün bağlanır. Sonra xüsusi bir maşının hovuzun döşəməsini süpürə bilməsi üçün yenidən konfiqurasiya edilməlidir. Maşın işinə sol üst hüceyrədən başlayır və hər hüceyrədən dəqiq bir dəfə keçərək sol alt hüceyrədə bitirməlidir. Şəklin sağ tərəfində belə bir yenidən konfiqurasiya göstərilir, burada altı baryer dəyişdirilmişdir. Lakin bu nümunə üçün dörd baryer dəyişdirilməsi kifayət edərdi.
Verilmiş bir hovuz konfiqurasiyasına əsasən, hovuzu yuxarıda göstərildiyi kimi yenidən konfiqurasiya etmək üçün lazım olan minimum baryer dəyişikliklərinin sayını müəyyən edən bir proqram yazmalısınız. Hovuzu yuxarıda göstərildiyi kimi yenidən konfiqurasiya etmək üçün həmişə ən azı bir mümkün yol var.
Hər test halı bir neçə sətirdən istifadə edərək təsvir edilir. İlk sətir hovuzun 2N sıra və 2N+1 sütunlu olduğunu göstərən bir tam ədəd N ehtiva edir (1 ≤ N ≤ 300). Növbəti 2N-1 sətirin hər biri baryerlərin istiqamətini təsvir edən N simvoldan ibarət bir sətir ehtiva edir. i-ci sətirdə, j-ci simvol, orta nöqtəsi koordinatlarda (i, 2j-1) olan baryerin istiqamətini göstərir, əgər i təkdirsə, və ya (i, 2j) əgər i cütdür, i = 1, 2, ..., 2N-1 və j = 1, 2, ..., N üçün. Simvol böyük hərflə 'V' əgər istiqamət şaqulidirsə, və ya böyük hərflə 'H' əgər üfüqidirsə.
Hər test halı üçün hovuzu yuxarıda göstərildiyi kimi yenidən konfiqurasiya etmək üçün lazım olan minimum baryer dəyişikliklərinin sayını təmsil edən bir tam ədəd ilə bir sətir çıxarın.
Nümunə 1