მინიმალური მობრუნება

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

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

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

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

წყარო: USACO, 2007/08, OCT, SILVER


მოცემულია N x N (1 <= N <= 100) ზომის მართკუთხა ველი, რომელიც დაყოფილია 
1*1-ზე კვადრატებად. ზოგიერთი კვადრატი არის გაუვალი და მონიშნულია'x'-ით. 
აქ მაგალითად მოცემულია 5 * 5-ზე მინდორი: . . B x . . x x A . . . . x . . x . . . . . x . . თავიდან ბესი არის A კვადრატში და უნდა გადავიდეს B-ში. ის მოძრაობს კვადრატის გვერდების პარალელურად. ბესის არ უყვარს მობრუნება. მოცემული ველისათვის
იპოვეთ ისეთი ბილიკი, რომელიც საჭიროებს ბესის რაც შეიძლება ნაკლებჯერ მობრუნებას და მისვლას A-დან B კვადრატში. საწყის და საბოლოო კვადრატებში ბესის თავი ნებისმიერი (ანუ საჭირო) მიმართულებითაა. A-დან B-ში მისვლა გარანტირებულია. შეტანის ფორმატი: * ხაზი 1: ერთი მთელი რიცხვი: N * ხაზები 2..N + 1: ხაზი i+1 არის i-ური ველი N სიმბოლოდან, როგორც ზემოთ იყო (მაგალითად '.', 'x', 'A', და 'B'); ხაზი არ შეიცავს ჰარს შეტანის ფორმატი: * ხაზი 1: ერთი მთელი, მობრუნებათა ის უმცირესი რაოდენობა, რომელიც უნდა გააკეთოს ბესიმ.



მაგალითები

შესატანი მონაცემები
3 .xA ... Bx. დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

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