একটি প্রদত্ত ম্যাট্রিক্সে, উপাদানের অবস্থান বিশ্লেষণ করার জন্য চারটি বস্তু রয়েছে:বাম, ডান, নীচে এবং শীর্ষ৷
ব্রেডথ ফার্স্ট সার্চ প্রদত্ত 2-ডি ম্যাট্রিক্সের দুটি উপাদানের মধ্যে সবচেয়ে কম দূরত্ব খুঁজে পাওয়া ছাড়া আর কিছুই নয়। এইভাবে, প্রতিটি কক্ষে, আমরা চারটি অপারেশন করতে পারি যা চারটি সংখ্যায় প্রকাশ করা যেতে পারে যেমন,
- '2' বর্ণনা করে যে ম্যাট্রিক্সের সেলটি উৎস।
- '3' বর্ণনা করে যে ম্যাট্রিক্সের সেল হল গন্তব্য।
- '1' বর্ণনা করে যে সেলটিকে আরও একটি দিকে সরানো যেতে পারে।
- '0' বর্ণনা করে যে ম্যাট্রিক্সের কোষটি কোন দিকে সরানো যায় না।
অ্যাডোব ন্যায্যতার ভিত্তিতে, আমরা একটি প্রদত্ত ম্যাট্রিক্সে একটি ব্রেডথ ফার্স্ট সার্চ অপারেশন করতে পারি৷
এই সমস্যা সমাধানের পদ্ধতি
সম্পূর্ণ ম্যাট্রিক্স অতিক্রম করার এবং BFS ব্যবহার করে যেকোন কক্ষের মধ্যে সর্বনিম্ন বা সর্বনিম্ন দূরত্ব খুঁজে বের করার অ্যালগরিদম নিম্নরূপ:
- প্রথমে সারি এবং কলামের ইনপুট নিন।
- প্রদত্ত সারি এবং কলাম দিয়ে একটি ম্যাট্রিক্স শুরু করুন।
- একটি পূর্ণসংখ্যা ফাংশন shortestDist(int row, int col, int mat[][col]) সারি, কলাম এবং ম্যাট্রিক্সকে ইনপুট হিসাবে নেয় এবং ম্যাট্রিক্সের উপাদানগুলির মধ্যে সবচেয়ে কম দূরত্ব প্রদান করে।
- উৎস এবং গন্তব্য উপাদান খুঁজে বের করতে পরিবর্তনশীল উৎস এবং গন্তব্য শুরু করুন।
- উপাদানটি '3' হলে সেটিকে গন্তব্য হিসেবে চিহ্নিত করুন এবং উপাদানটি যদি '2' হয়, তাহলে সেটিকে উৎস উপাদান হিসেবে চিহ্নিত করুন।
- প্রদত্ত ম্যাট্রিক্সে ব্রেডথ ফার্স্ট সার্চ প্রয়োগ করতে এখন সারি ডেটা কাঠামো শুরু করুন৷
- ম্যাট্রিক্সের সারি এবং কলাম জোড়া হিসাবে সারিতে ঢোকান। এখন ঘরে যান এবং এটি একটি গন্তব্য সেল কিনা তা খুঁজে বের করুন। যদি গন্তব্য সেলের দূরত্ব বর্তমান সেলের থেকে ন্যূনতম বা কম থাকে, তাহলে দূরত্ব আপডেট করুন৷
- বর্তমান সেল থেকে সেলের ন্যূনতম দূরত্ব জানতে আবার অন্য দিকে যান।
- আউটপুট হিসাবে সর্বনিম্ন দূরত্ব ফেরত দিন।
উদাহরণ
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
