दिए गए matrix में, element position analyze करने के लिए चार objects हैं: left, right, bottom, और top।
Breadth First Search दिए गए 2-D Matrix के दो elements के बीच shortest distance ढूंढने के अलावा कुछ नहीं है। इस प्रकार, प्रत्येक cell में चार operations perform की जा सकती हैं जिन्हें चार numerals में express किया जा सकता है:
- '2' describe करता है कि matrix में cell Source है।
- '3' describe करता है कि matrix में cell Destination है।
- '1' describe करता है कि cell को किसी direction में further move किया जा सकता है।
- '0' describe करता है कि matrix में cell को किसी direction में move नहीं किया जा सकता।
उपरोक्त justification के आधार पर, हम दिए गए Matrix पर Breadth First Search Operation perform कर सकते हैं।
Problem हल करने का दृष्टिकोण
पूरे matrix को traverse करके BFS का उपयोग करके elements के बीच minimum या shortest distance ढूंढने का algorithm इस प्रकार है:
- सबसे पहले row और column का input लें।
- दिए गए row और column के साथ matrix initialize करें।
- एक integer function shortestDist(int row, int col, int mat[][col]) row, column और matrix को input के रूप में लेता है और matrix के elements के बीच shortest distance return करता है।
- Source और destination ढूंढने के लिए variable source और destination initialize करें।
- यदि element '3' है, तो इसे destination mark करें और यदि element '2' है, तो इसे source element mark करें।
- अब Breadth First Search को दिए गए matrix पर implement करने के लिए queue data structure initialize करें।
- Matrix के row और column को pairs के रूप में queue में insert करें। अब cell में move करें और पता करें कि यह destination cell है या नहीं। यदि destination cell की distance minimum या current cell से कम है, तो distance update करें।
- फिर current cell से cell की minimum distance ढूंढने के लिए दूसरी direction में move करें।
- Minimum distance को output के रूप में return करें।
उदाहरण
import queue
INF = 10000
class Node:
def __init__(self, i, j):
self.row_num = i
self.col_num = j
def findDistance(row, col, mat):
source_i = 0
source_j = 0
destination_i = 0
destination_j = 0
for i in range(0, row):
for j in range(0, col):
if mat[i][j] == 2:
source_i = i
source_j = j
if mat[i][j] == 3:
destination_i = i
destination_j = j
dist = []
for i in range(0, row):
sublist = []
for j in range(0, col):
sublist.append(INF)
dist.append(sublist)
# initialise queue to start BFS on matrix
q = queue.Queue()
source = Node(source_i, source_j)
q.put(source)
dist[source_i][source_j] = 0
# modified BFS by add constraint checks
while not q.empty():
# extract and remove the node from the front of queue
temp = q.get()
x = temp.row_num
y = temp.col_num
# If move towards left is allowed or it is the destnation cell
if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3):
# if distance to reach the cell to the left is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x][y - 1]:
dist[x][y - 1] = dist[x][y] + 1
next = Node(x, y - 1)
q.put(next)
# If move towards right is allowed or it is the destination cell
if y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3):
# if distance to reach the cell to the right is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x][y + 1]:
dist[x][y + 1] = dist[x][y] + 1
next = Node(x, y + 1)
q.put(next)
# If move towards up is allowed or it is the destination cell
if x - 1 >= 0 and (mat[x - 1][y] == 1 or mat[x-1][y] == 3):
# if distance to reach the cell to the up is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x - 1][y]:
dist[x - 1][y] = dist[x][y] + 1
next = Node(x - 1, y)
q.put(next)
# If move towards down is allowed or it is the destination cell
if x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3):
# if distance to reach the cell to the down is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x + 1][y]:
dist[x + 1][y] = dist[x][y] + 1
next = Node(x + 1, y)
q.put(next)
return dist[destination_i][destination_j]
row = 5
col = 5
mat = [
[1, 0, 0, 2, 1],
[1, 0, 2, 1, 1],
[0, 1, 1, 1, 0],
[3, 2, 0, 0, 1],
[3, 1, 0, 0, 1]
]
answer = findDistance(row, col, mat)
if answer == INF:
print("No Path Found")
else:
print("The Shortest Distance between Source and Destination is:")
print(answer)
आउटपुट
The Shortest Distance between Source and Destination is: 2
