पायथन में लक्ष्य तक पहुंचने के लिए सबसे छोटा रास्ता खोजने का प्रोग्राम

मान लीजिए हमें एक ग्रिड दिया गया है जहां सेल में विभिन्न सिंबल जैसे 'X', 'O', '*' और '#' होते हैं और सिंबल के विभिन्न अर्थ होते हैं।

• '#' लक्ष्य सेल है जिसे हम पहुंचना चाहते हैं।
• 'O' एक फ्री सेल है जिसके माध्यम से हम लक्ष्य सेल तक यात्रा कर सकते हैं।
• '*' सेल में हमारी पोजीशन है।
• 'X' एक ब्लॉक्ड सेल है, जिसके माध्यम से हम यात्रा नहीं कर सकते।

हमें ग्रिड में अपनी वर्तमान पोजीशन से लक्ष्य सेल तक पहुंचने के लिए आवश्यक चालों की संख्या ढूंढनी है। यदि लक्ष्य पहुंच योग्य नहीं है, तो हम -1 वापस करते हैं। ग्रिड को प्रोग्राम में इनपुट के रूप में दिया जाता है।

उदाहरण के लिए, यदि इनपुट है:

तो आउटपुट 2 होगा।

हल करने के चरण

1. m := grid की पंक्ति संख्या
2. n := grid की कॉलम संख्या
3. i को 0 से m तक लूप चलाएं:
   • j को 0 से n तक लूप चलाएं:
     • यदि grid[i][j] == "*", तो लूप से बाहर निकलें।
     • अन्यथा, अगले इटरेशन पर जाएं।
   • लूप से बाहर निकलें।
4. ans := 0
5. queue := इंटीजर जोड़ी (i, j) वाली नई सूची
6. grid[i][j] := "X"
7. queue खाली न होने तक व्हाइल लूप चलाएं:
   • ans := ans + 1
   • newq := एक नई सूची
   • queue में प्रत्येक i, j के लिए:
     • (i-1, j), (i, j-1), (i, j+1), (i+1, j) में प्रत्येक ii, jj के लिए:
       • यदि 0 <= ii < m और 0 <= jj < n और grid[ii][jj] != "X", तो:
         • यदि grid[ii][jj] == "#", तो ans वापस करें।
         • ii, jj को newq के अंत में जोड़ें
         • grid[ii][jj] := "X"
   • queue := newq
8. -1 वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(grid):
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "*":
                break
            else:
                continue
            break
    ans = 0
    queue = [(i, j)]
    grid[i][j] = "X"
    while queue:
        ans += 1
        newq = []
        for i, j in queue:
            for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
                if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
                    if grid[ii][jj] == "#":
                        return ans
                    newq.append((ii, jj))
                    grid[ii][jj] = "X"
        queue = newq
    return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#', 'O', 'X'],['X', 'X', 'X', 'X']]))

इनपुट

[['X', 'X', 'O', 'X'], ['X', 'X', '*', 'X'], ['X', '#', 'O', 'X'], ['X', 'X', 'X', 'X']]

आउटपुट

2