ჭაობი

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

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

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

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

წყარო: GEOI, 2010, რეგიონული XI-XII კლასები


ჭაობი, რომელსაც მართკუთხედის ფორმა აქვს, n რაოდენობის სტრიქონისა და m რაოდენობის სვეტისაგან შედგება. სტრიქონები და სვეტები ერთეულოვანი სიგრძის გვერდის მქონე კვადრატულ უჯრებადაა დაყოფილი. ამ უჯრებიდან ზოგიერთი ნიადაგიან უბანს გამოსახავს, ზოგიერთი კი წყლიანს. ნიადაგი აღინიშნება 0-ით, ხოლო წყალი კი – 1-ით. ჩვენი მიზანია მოვძებნოთ მარშრუტი, რომელიც ჩრდილოეთ (ზედა) სანაპიროდან სამხრეთ (ქვედა) სანაპიროზე მიგვიყვანს ისე, რომ წყლიან უჯრებზე არ გავიაროთ. თუმცა, ჩვენ შესაძლებლობა გვაქვს წყლიანი უჯრა გავლადი გავხადოთ მასზე ტივტივა ხიდის გადადებით (ასეთი ხიდების რაოდენობა საკმარისად გვაქვს და, თანაც, მათი საჭირო რაოდენობის გამოყენებით შესაძლებელია მიმდევრობით განლაგებულ რამდენიმე წყლიან უჯრაზე გავლაც). რადგანაც ასეთ ხიდზე სიარული სახიფათოა, ჩვენ გვსურს მათი მინიმალური რაოდენობის გამოყენება. ერთ ბიჯზე შესაძლებელია მხოლოდ ერთი უჯრის გავლა ჰორიზონტალურად, ვერტიკალურად ან დიაგონალურად. 

დაწერეთ პროგრამა, რომელიც იპოვის ტივტივა ხიდების იმ მინიმალურ რაოდენობას, რომელიც საჭიროა ჩრდილოეთ სანაპიროდან სამხრეთ სანაპირომდე მისაღწევად.

შესატანი მონაცემები:  პირველ სტრიქონში მოცემულია ერთი ჰარით გამოყოფილი ორი მთელი დადებითი n და m რიცხვი (3≤n,m≤100) - ჭაობის სტრიქონებისა და სვეტების რაოდენობა, შესაბამისად (სტრიქონებისა და სვეტების გადანომვრა 1-დან იწყება).  მომდევნო n რაოდენობის სტრიქონიდან თითოეულში ჩაწერილია თითო ჰარით გამოყოფილი მ რაოდენობის ორობითი ციფრი, რომლებიც ჭაობის სტრუქტურას გამოსახავენ (0-ნიადაგი, 1-წყალი).

გამოსატანი მონაცემები:  ერთადერთ სტრიქონში უნდა ჩაიწეროს ერთი მთელი რიცხვი - ტივტივა ხიდების ის მინიმალური რაოდენობა, რომელიც საჭიროა ჩრდილოეთ სანაპიროდან სამხრეთ სანაპირომდე მისაღწევად.

 




მაგალითები

შესატანი მონაცემები
8 9 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

განმარტება: ტივტივა ხიდების მინიმალური რაოდენობა, რომელიც დაგვჭირდება ჩრდილოეთ სანაპიროდან სამხრეთ სანაპირომდე მისაღწევად 2-ის ტოლია. ერთი მათგანი უნდა გადავდოთ უჯრაზე კოორდინატებით (4,5), ხოლო მეორე კი – უჯრაზე კოორდინატებით (7,8).