একটি দিয়া ম্যাট্রিক্সে এলিমেন্ট পজিশন বিশ্লেষণ করার চারটি ডিরেকশন রয়েছে: লেফট, রাইট, বটম, এবং টপ।
ব্রেডথ ফার্স্ট সার্চ (BFS) হলো একটি দিয়া ২-ডি ম্যাট্রিক্সের দুটি এলিমেন্টের মধ্যকার শর্টেস্ট ডিস্ট্যান্স (shortest distance) বের করা। প্রতিটি সেলে চারটি অপারেশন করা যায় যেগুলো চারটি নম্বর দিয়ে এক্সপ্রেস করা যায়:
- '২' = সেলটি ম্যাট্রিক্সে সোর্স (Source)।
- '৩' = সেলটি ম্যাট্রিক্সে ডেস্টিনেশন (Destination)।
- '১' = সেলটি একটি ডিরেকশনে আগে যেতে পারে।
- '০' = সেলটি কোনো ডিরেকশনে যেতে পারে না।
উপরের জাস্টিফিকেশন অনুযায়ী দিয়া ম্যাট্রিক্সের ওপর BFS অপারেশন করা যায়।
সমস্যা সমাধানের পদ্ধতি
পুরো ম্যাট্রিক্স ট্রাভার্স করে BFS ব্যবহার করে যেকোনো সেলের মিনিমাম বা শর্টেস্ট ডিস্ট্যান্স বের করার অ্যালগরিদম:
প্রথমে রো এবং কলাম ইনপুট নিন।
দিয়া রো এবং কলাম দিয়ে ম্যাট্রিক্স ইনিশিয়ালাইজ করুন।
একটি ইন্টিজার ফাংশন shortestDist(int row, int col, int mat[][col]) রো, কলাম এবং ম্যাট্রিক্স ইনপুট নেয় এবং ম্যাট্রিক্সের এলিমেন্টগুলোর শর্টেস্ট ডিস্ট্যান্স রিটার্ন করে।
সোর্স এবং ডেস্টিনেশন ভেরিয়েবল ইনিশিয়ালাইজ করুন সোর্স এবং ডেস্টিনেশন এলিমেন্ট খুঁজে বের করতে।
যদি এলিমেন্ট '৩' হয়, তবে সেটাকে ডেস্টিনেশন মার্ক করুন এবং যদি '২' হয়, তবে সোর্স এলিমেন্ট মার্ক করুন।
এখন BFS ইমপ্লিমেন্ট করতে কিউ (queue) ডেটা স্ট্রাকচার ইনিশিয়ালাইজ করুন।
ম্যাট্রিক্সের রো এবং কলাম কিউ-তে পেয়ার হিসেবে ইনসার্ট করুন। এখন সেলে মুভ করে চেক করুন ডেস্টিনেশন সেল কিনা। যদি ডেস্টিনেশন সেলের ডিস্ট্যান্স কারেন্ট সেল থেকে কম হয়, তবে ডিস্ট্যান্স আপডেট করুন।
আরেক ডিরেকশনে মুভ করে কারেন্ট সেল থেকে মিনিমাম ডিস্ট্যান্স বের করুন।
আউটপুট হিসেবে মিনিমাম ডিস্ট্যান্স রিটার্ন করুন।
উদাহরণ
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)
# BFS শুরু করার জন্য কিউ ইনিশিয়ালাইজ
q = queue.Queue()
source = Node(source_i, source_j)
q.put(source)
dist[source_i][source_j] = 0
# কনস্ট্রেইন্ট চেকসহ মডিফাইড BFS
while (not q.empty()):
# কিউর ফ্রন্ট থেকে নোড এক্সট্র্যাক্ট ও রিমুভ
temp = q.get()
x = temp.row_num
y = temp.col_num
# বামে মুভ আলাউড বা ডেস্টিনেশন সেল হলে
if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3):
# বামের সেলে পৌঁছানোর ডিস্ট্যান্স প্রিভিয়াস পাথ থেকে কম হলে আপডেট
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 y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3):
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 x - 1 >= 0 and (mat[x - 1][y] == 1 or mat[x-1][y] == 3):
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 x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3):
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
