मान लीजिए हमारे पास एक N x N मैट्रिक्स M है, जो 1, 0, 2, 3 से भरा है। हमें स्रोत सेल से गंतव्य सेल तक जाने के लिए आवश्यक न्यूनतम चालों की संख्या ढूंढनी है। केवल खाली सेलों से गुजरते हुए, हम ऊपर, नीचे, दाएं और बाएं जा सकते हैं।
मान 1 वाला सेल स्रोत दर्शाता है।
मान 2 वाला सेल गंतव्य दर्शाता है।
मान 3 वाला सेल खाली सेल दर्शाता है।
मान 0 वाला सेल दीवार दर्शाता है।
केवल एक स्रोत और केवल एक गंतव्य सेल होगा। स्रोत सेल से गंतव्य तक पहुंचने के लिए एक से अधिक पथ हो सकते हैं। अब, मैट्रिक्स में प्रत्येक चाल को '1' माना जाता है।
तो, यदि इनपुट इस तरह है:
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
तो आउटपुट 5 होगा,
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
शुरुआत से गंतव्य तक हरा पथ सबसे छोटा है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
nodes := order * order + 2
g := 'nodes' संख्या के शीर्षों वाला एक खाली ग्राफ
k := 1
i को 0 से order तक के लिए, करें:
j को 0 से order तक के लिए, करें:
यदि mat[i, j], 0 के समान नहीं है, तो:
यदि is_ok(i, j+1, mat) शून्येतर है, तो:
g के k और k+1 नोड्स के बीच एक किनारा बनाएं
यदि is_ok(i, j-1, mat) शून्येतर है, तो:
g के k, k-1 नोड्स के बीच एक किनारा बनाएं
यदि j < order-1 और is_ok(i+1, j, mat) शून्येतर है, तो:
g के k, k+order नोड्स के बीच एक किनारा बनाएं
यदि i > 0 और is_ok(i-1, j, mat) शून्येतर है, तो:
g के k, k-order नोड्स के बीच एक किनारा बनाएं
यदि mat[i, j], 1 के समान है, तो:
src := k
यदि mat[i, j], 2 के समान है, तो:
dest := k
k := k + 1
g पर src से dest तक BFS करें और लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
class Graph: def __init__(self, nodes): self.nodes = nodes self.adj = [[] for i in range(nodes)] def insert_edge (self, src , dest): self.adj[src].append(dest) self.adj[dest].append(src) def BFS(self, src, dest): if (src == dest): return 0 level = [-1] * self.nodes queue = [] level[src] = 0 queue.append(src) while (len(queue) != 0): src = queue.pop() i = 0 while i < len(self.adj[src]): if (level[self.adj[src][i]] < 0 or level[self.adj[src][i]] > level[src] + 1 ): level[self.adj[src][i]] = level[src] + 1 queue.append(self.adj[src][i]) i += 1 return level[dest] def is_ok(i, j, mat): global order if ((i < 0 or i >= order) or (j < 0 or j >= order ) or mat[i][j] == 0): return False return True def get_min_math(mat): global order src , dest = None, None nodes = order * order + 2 g = Graph(nodes) k = 1 for i in range(order): for j in range(order): if (mat[i][j] != 0): if (is_ok (i , j + 1 , mat)): g.insert_edge (k , k + 1) if (is_ok (i , j - 1 , mat)): g.insert_edge (k , k - 1) if (j < order - 1 and is_ok (i + 1 , j , mat)): g.insert_edge (k , k + order) if (i > 0 and is_ok (i - 1 , j , mat)): g.insert_edge (k , k - order) if(mat[i][j] == 1): src = k if (mat[i][j] == 2): dest = k k += 1 return g.BFS (src, dest) order = 4 mat = [[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]] print(get_min_math(mat))
इनपुट
[[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]
आउटपुट
0
