ჯადოსნური ფეხსაცმელები

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

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

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

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

წყარო: USACO, 2005/06, MAR, BRONZE


 
ერთ დღეს, ბალახობისას, ბეტსიმ იპოვა 4 ცალი ჯადოსნური ფეხსაცმელი! ბეტსიმ ისინი ჩაიცვა და აღმოაჩინა რომ 
ისინი ეხმარებიან მას იხტუნოს მინდორზე, რომელიც, რა თქმა უნდა, დაყოფილია მოხერხებულ ბადედ R ხაზი
(1 <= R <= 50) და C სვეტი (1 <= C<= 50). ფეხსაცმელები ეხმარება მას გადახტეს 2 განსხვავებული გზით:
ერთი - მსგავსად ჭადრაკის მხედრისა, მეორე - წესით, რომელიც არ უნახავს მანამდე. ბეტსიმ შეამჩნია, რომ ხტება
მხედრის სვლით თავის 1-ელ, მე-3, მე-5 და ა. შ. კენტ სვლებზე, ხოლო მე-2, მე-4 და ა. შ. ლუწ სვლებზე ის
გადაადგილდება სხვანაირად. რუკებზე მოცემულია, თუ როგორ შეუძლია მას გადაადგილება: მხედარი (კენტი სვლები) სხვა (ლუწი სვლები) . . K . K . . . . . O . . . . K . . . K . . . . . . . . . . . B . . . . O . B . O . . K . . . K . . . . . . . . . . K . K . . . . . O . . .
როცა ბეტსი იწყებს 'B' უჯრაში, იმის მიხედვით თუ რომელია მისი შემდეგი სვლა, კენტი, თუ ლუწი, მას შეუძლია 
გადახტეს შესაბამისად რომელიმე'K' ან 'O' უჯრაში. მიხვდა რა, რომ მას შეუძლია იმოძრაოს გაცილებით სწრაფად,
უნდა იცოდეს რამდენი ხანი დასჭირდება გადახტეს ჯადოსნური ფეხსაცმელებით ფერმერი ჯონის რძიან კამფეტებამდე,
რომელიც შემთხვევით დაუცვივდა ჯონს ფერმაში ბოლო ვიზიტისას.
მოცემულია მინდვრის ზომები, ბეტსის და კამფეტების მდებარეობა. იპოვეთ ჯადოსნურ ნახტომთა მინიმალური რაოდენობა, 
რომელიც დასჭირდება ბეტსის, რათა მიაღწიოს კამფეტებიან უჯრამდე. მას არ შეუძლია გადახტეს მინდვრის გარეთ, მაგრამ
ზუსტად იცის, რომ ყოველთვის შესაძლებელია აიღოს კამფეტები (ანუ დაეშვას კამფეტებიან უჯრაზე). შეტანის ფორმატი: * სტრიქონი 1: ორი ჰარით გამოყოფილი მთელი R და C.
* სტრიქონი 2: ორი ჰარით გამოყოფილი მთელი, ბეტსის საწყისი მდებარეობის სტრიქონი და სვეტი.
* სტრიქონი 3: ორი ჰარით გამოყოფილი მთელი, კამფეტების მდებარეობის სტრიქონი და სვეტი.
გამოტანის ფორმატი: * სტრიქონი 1: ერთი მთელი, კამფეტების უჯრამდე მისვლისათვის საჭირო ნახტომების უმცირესი რაოდენობა.



მაგალითები

შესატანი მონაცემები
4 5 4 1 4 3 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება

შენიშვნა

შეტანის დეტალები:

. . . . .
. . . . . 
. . . . . 
B . C . . 

გამოტანის დეტალები:

აქ მოცემულია ერთ-ერთი გზა:
. . . . .
. 1 . 2 .
. . . . .
B . 3 . .