एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

रोबोटों की अदला-बदली

आप एक ऐसे स्टार्टअप में काम कर रहे हैं जो Boston Dynamics को टक्कर देने की कोशिश कर रहा है। इस चुनौती में दो रोबोटों को एक ग्रिड पर इस तरह अपनी जगहें बदलनी हैं कि वे एक-दूसरे के ऊपर न आ पाएं।
यह ग्रिड ऊँचाई h और चौड़ाई w की होती है, जिसमें फर्श को बिंदुओं (.) से और दीवारों को हैशटैग (#) से दर्शाया गया है।
रोबोट अपने आस-पास की आठों दिशाओं (ऊर्ध्वाधर, क्षैतिज और विकर्ण) में चल सकते हैं, लेकिन दीवारों या एक-दूसरे के स्थान पर कदम नहीं रख सकते। हर चरण में दोनों रोबोट या तो कोई चाल चल सकते हैं, या अपनी जगह पर ही रुक सकते हैं। एक ही चरण में वे एक-दूसरे को पार नहीं कर सकते।
आपको यह पता लगाना है कि न्यूनतम कितने चरणों (steps) में पहले रोबोट को दूसरे की मूल जगह पर और दूसरे रोबोट को पहले की मूल जगह पर लाया जा सकता है।

इनपुट

इनपुट की पहली पंक्ति में दोपूर्णांक h और w होते हैं (1 ≤ h, w ≤ 50)।
अगली h पंक्तियों में ग्रिड को दर्शाने वाले w अक्षर होते हैं।
पहला रोबोट अक्षर A द्वारा और दूसरा रोबोट अक्षर B द्वारा दर्शाया गया है।

आउटपुट

कार्यक्रम को रोबोटों की अदला-बदली के लिए आवश्यक चरणों की न्यूनतम संख्या प्रिंट करनी चाहिए। यदि ऐसा संभव न हो, तो Impossible प्रिंट करना होगा।

उदाहरण

Input

4 4
AB.#
###.
...#
.###
Output

11
Input

2 2
AB
..
Output

2
Input

1 3
A.B
Output

Impossible
 

Constraints

Time limit: 15 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue