რობინზონი

დროის ლიმიტი: 3 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 15, ეტაპი 1


შტორმის გამო უკაცრიელ კუნძულზე გამორიყულამ რობინზონმა ააშენა გემი, რათა გასულიყო ზღვაში და მიეგნო ადამიანთა დასახლებისთვის. იგი გამოცდილი მეზღვაურია, შესაბამისად გემი ყველა წესის დაცვით ააგო : მას აუცილებლად აქვს სიმეტრიის ღერძი და გემისთვის დამახასიათებელი სწორი ფორმა. ცხვირთან არის ვიწრო, ცენტრისაკენ ნელნელა ფართოვდება, ხოლო კიჩოსკენ ისევ იწყებს დავიწროვებას. ეს კი აღნიშნავს, რომ გემის რაღაც ნაწილი არის უფრო განიერი ვიდრე კიჩო და ცხვირი.

სამწუხაროდ ადგილი, სადაც რობინზონმა თავისი გემი გაუშვა წყალში სავსეა წყალმცენარეებით. ამავვდროულად ეს წყალმცენარეების იმდენად უხეში და მაგარია, რომ გემს არ შეუძლია მათ მიერ დაკავებულ ადგილებში ცურვა. იმედია რობინზონი სწორი მანევრირებით შეძლებს ღია ზღვაში გასვლას.

გემს შეიძლია მხოლოდ წინ, უკან, მარჯვნივ და მარცხნიც გადაადგილება, მაგრამ არ შეუძლია მოტრიალება.

თქვენი დავალებაა, გაარკვიოთ შეუძლია თუ არა რობინზონს ღია ზღვაში გასვლა.

სიმარტივისთვის კუნძული და მის შემოგარენი წარმოდგენილია, როგორც კვადრატული რუკა დაყოფილი ერთეულოვან კვადრატებად, რომელთაგან თითოეული შეიძლება წარმოადგენდეს წყლალს, რობინზონის გემს ან წინააღმდეგობას (მიწა ან წყალმცენარე). გემი არის ოთხი მიმართულებიდან ერთ-ერთის პარალელური და რუკის დანაყოფების ერთ-ერთი ხაზი იდეალურად გასდევს გემის სიმეტრიის ღერძს და ყოფს მას ორ სიმეტრიულ ნაწილად.

ჩავთვალოთ, რომ რუკის გარეთ არის ღია ზღვა, რომელშიც რობინზონი შეძლებს გასვლას თუ მთლიანი გემი დატოვებს რუკის ტერიტორიას. ერთ მოძრაობად ითვლება გემის გადაადგილება 1 ერთეულით შესაბამისი მიმართულებით (ჩრდილოეთი, სამხრეთი, აღმოსავლეთი, დასავლეთი). გადაადგილება შესაძლებელია თუ გემი გადაადგილებამდე და მის შემდგემ მთლიანად იმყოფება წყალში.

თქვენი ამოცანაა წაიკითხოთ შემომავალი რუკა, დათვალოთ მინიმალური გადაადგილებების რაოდენობა, რომელიც საჭიროა გემის ზღვაში გასასვლელად და ეს გამოთვლილი რაოდენობა დაბეჭდოთ.

შესატანი მონაცემები:

            თავდაპირველად შემოგდით n ( 3 <= n <= 2000), რომელიც აღნიშნავს, რუკის გვერდის სიგრძეს. შემდგომი n ხაზი შედგება n ცალი სიმბოლოსგან.  თითოეული ხაზი აღნიშნავს რუკაზე i-ურ სტრიქონს, ხოლო თითუელი ხაზის j+1 სიმბოლო აღნიშნავს რუკის (i, j) კოორდინატის მდგომარეობას.  რუკაში შეხვდებით 3 სიმბოლოს:

Ø  “.” - დაკავებულია წყლით (წერტილი)

Ø  “X” - დაკავებულია დაბრკოლებით (ხმელეთი ან წყალმცენარე)

Ø  “r” - დაკავებულია რობინზონის გემით

გამოსატანი მონაცემები :

          პროგრამამ უნდა გამოიტანოს 1 დადებითი ინტეჯერი, რომელიც აღნიშნავს გადაადგილებათა იმ მინიმალურ რაოდენობას რომელიც საჭიროა, რათა რობინზონის გემმა მთლიანად დატოვოს რუკის ტერიოტრია. თუ ეს შეუძლებელია გამოიტანეთ “NO”.  (გაითვალისწინეთ რომ პროგრამამ უნდა გამოიტანოს მხოლოდ 1 ინტეჯერი ან სიტყვა “NO”)




მაგალითები

შესატანი მონაცემები
10 .......... .......... ..r....... .rrrX..... rrrrr..... .rrr...... X.r....... .Xr....... .......... .......... დაკოპირება
გამოსატანი მონაცემები
10 დაკოპირება

შენიშვნა

 

 

 

თარგმანი შესრულებულია ლევან აფაქიძის მიერ.