A - Topological Map 解説
by
nikaj
პირდაპირი ამოხსნა არის ანელირება, ყოველ ჯერზე ერთი ელემენტის შეცვლა რომელიმე მეზობლის ფერით. ეს ამოხსნა ალბათ ტესტზე სადღაც \(2000\) ქულას იძლევა. შეგვიძლია დროებით დავუშვათ არასწორი მდგომარეობები (ყველაზე ადვილად გამოსწორებადია ზედმეტი წიბოს წარმოშობა) თუმცა ეს ბევრს არ მოგვცემს.
მთავარი პრობლემაა გრძელი კომპონენტების წარმოშობა რომელსაც ასეთი ცვლილებებით ვერ გამოვასწორებთ. რაღაც ასეთი:
123
123
123
ცხადია შეგვიძლია აქ შუა ამოვჭრათ და ერთ-ერთი მხარე წავძრათ. ამას ბევრი სპეციალური კოდი ჭირდება და შემდეგი პრობლემა გვექნება მსგავსი, ოღონდ ზიგზაგური გზები რომლის გამოსწორება ბევრად უფრო რთულია.
ამ პრობლემის გადაჭრის ერთი გზაა მთლიანი სტრიქონების და სვეტების წაშლა. თუ ორი მეზობელი სტრიქონი (ან სვეტი) ტოლია, ერთერთის წაშლა პირდაპირ შეიძლება. თუმცა ეს არაა აუცილებელი პირობა, ზოგჯერ სხვებიც იშლება თუმცა დამატებითი შემოწმებებით. კერძოდ, სვეტის წაშლა მარტივია თუ მასში ყოველ ელემენტს აქვს მეზობელი ტოლი მარცხნივ ან მარჯვნივ. თუ ასეთ წაშლებს გავაკეთებთ, ზომები შემცირდება და ზემოთ ნახსენები პრობლემა აღარ იქნება ისეთი ცუდი.
ჩემო ამოხსნა (\(335605\) ქულა) ზუსტად ასეთია: ჯერ 1 წამი ვცდილობთ ცხრილის შეცვლას ისე, რომ ასეთი წაშლადები გაჩნდეს (აქაც ანელირებით, ოღონდ ვცდილობთ ტოლი მეზობლების რაოდენობა ვზარდოთ) და მეორე 1 წამი ეთმობა საბოლოო ანელირებას.
შესაძლებელია ასევე ამ ორის გაერთიანება და ერთდროულად კეთება.
თუმცა, უკეთესი ამოხსნა, რომელიც საჭიროა \(336K\)-ქულისთვის საჭიროებს უკეთეს იდეას. ეს იდეაა ერთდროულად 2 უჯრის ცვლილება.
AB
CD
აქ თუ A ხდება მეზობელი B-ს ტოლი, მისი პერპენდიკულარული მეზობელი C გახდება D-ს ტოლი და ეს მაგიურად აგვარებს გრძელი გზების პრობლემას. ასეთია ყველა ტოპ ამოხსნა.
投稿日時:
最終更新: