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

ग्रिड पर सबसे छोटा पथ (Shortest Path on a Grid)

एक भूलभुलैया, जो r पंक्तियों और c स्तंभों वाले ग्रिड के रूप में दर्शाया गया है, में आपको प्रारंभिक कोश (starting cell) से अंतिम कोश (end cell) तक जाने वाले सबसे छोटे रास्ते की लंबाई खोजनी है।
इस भूलभुलैया को निम्नलिखित तरीके से दर्शाया गया है:
  • फ़्लोर (floor) को . (डॉट) से दिखाया जाता है।
  • दीवारों (walls) को # (हैशटैग) से दिखाया जाता है।
  • आरंभिक बिंदु (starting point) को बड़े अक्षर S से दर्शाया गया है।
  • अंतिम कोश (end cell) को बड़े अक्षर E से दर्शाया गया है।
यदि दो कोश दीवार नहीं हैं, तो आप बाएँ, दाएँ, ऊपर या नीचे किसी भी आसन्न कोश में जा सकते हैं।
आपसे अनुरोध है कि शुरुआती कोश S से अंतिम कोश E तक के सबसे छोटे रास्ते की लंबाई ज्ञात करें।

इनपुट (Input)

इनपुट की पहली पंक्ति में दो पूर्णांक r और c दिए जाते हैं (1 ≤ r, c ≤ 1000)।
इसके बाद की अगली r पंक्तियों में ग्रिड का वर्णन करने वाले c वर्ण मौजूद होते हैं। प्रत्येक कोश या तो फ़्लोर (.) है, दीवार (#) है, आरंभिक बिंदु (S) है, या अंतिम बिंदु (E) है। यह सुनिश्चित किया जाता है कि पूरे ग्रिड में केवल एक ही S और एक ही E मौजूद हों।

आउटपुट (Output)

प्रोग्राम को S से E तक जाने वाले सबसे छोटे रास्ते की लंबाई प्रिंट करनी चाहिए।

उदाहरण (Examples)

Input

5 8
########
##.S....
....#.#.
#......#
...#...E
Output

7
 
 
Tip
हमेशा ग्राफ़ को स्पष्ट रूप से बनाना ज़रूरी नहीं होता है ताकि उस पर BFS एल्गोरिथ्म चलाया जाए। कई बार आप ग्रिड जैसी संरचनाओं को एक इनडायरेक्ट या इम्प्लिसिट (implicit) ग्राफ़ मानकर सीधे BFS का इस्तेमाल कर सकते हैं।
Hint
आप इस ग्रिड को ही ग्राफ़ की तरह इस्तेमाल कर सकते हैं और एक द्विबिंदी (two-dimensional) ऐरे d[][] रख सकते हैं, जिसमें आरंभिक कोश से लेकर किसी भी वर्तमान कोश तक की सबसे छोटी दूरी संग्रहीत हो।
 

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