এই সমস্যায়, আমাদেরকে m X n আকারের একটি বর্গাকার ম্যাট্রিক্স ম্যাট [][][] দেওয়া হয়েছে প্রতিটি উপাদানের সাথে 0 বা 1। যদি একটি উপাদানের মান 1 থাকে, এর মানে এটি সংযুক্ত, যদি মানটি 0 হয়, তাহলে এর অর্থ হল এটি সংযুক্ত নয়। আমাদের কাজ হল বাইনারি ম্যাট্রিক্সে সর্বাধিক পথের দৈর্ঘ্য খুঁজে বের করা।
সমস্যা বর্ণনা − সমস্যা সমাধানের জন্য, আমাদের ম্যাট্রিক্সে সবচেয়ে বড় দৈর্ঘ্যের পথ খুঁজে বের করতে হবে, যার মানে ম্যাট্রিক্সের সমস্ত 1টি উপাদান। পথ খোঁজার আগে, আমরা সর্বাধিক একটি 0 থেকে 1 রূপান্তর করব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
mat[][] = {{1, 0},
{0, 1}} আউটপুট
3
ব্যাখ্যা
We can convert 0 at index (0, 1) or (1, 0) to maximise the path length.
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল প্রতিটি 0 থেকে 1 রূপান্তর করার পরে দৈর্ঘ্য খুঁজে বের করা। আমরা পথের দৈর্ঘ্য খুঁজে বের করার জন্য প্রথমে গভীরতা ব্যবহার করব এবং তারপরে সমস্ত পাথের দৈর্ঘ্যের সর্বাধিক ফেরত দেব।
একটি দক্ষ সমাধান হল একাধিক রূপান্তর করার প্রয়োজনীয়তা দূর করা এবং সবচেয়ে প্রতিশ্রুতিশীল সমাধান দেয় এমন একটির জন্য মীমাংসা করা। আমরা এমন একটি গোষ্ঠী খুঁজে পাব যাতে একটি 0 থেকে 1 এ পরিবর্তন করলে সবচেয়ে বড় দৈর্ঘ্যের পথ ফিরে আসবে।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
def FindNeighbor(R, C, N):
for nr, nc in (((R - 1), C), ( (R + 1) , C), (R, (C - 1) ), (R, (C + 1) )):
if 0 <= nr < N and 0 <= nc < N:
yield nr, nc
def DFSTraversal(R, C, index, mat, N):
maxLen = 1
mat[R][C] = index
for nr, nc in FindNeighbor(R, C, N):
if mat[nr][nc] == 1:
maxLen += DFSTraversal(nr, nc, index)
return maxLen
def findLargestPath(mat):
N = len(mat)
maxPath = {}
index = 2
for i in range(N):
for j in range(N):
if mat[i][j] == 1:
maxPath[index] = DFSTraversal(i, j, index, mat, N)
index += 1
maxPathLen = max(maxPath.values() or [0])
for i in range(N):
for j in range(N):
if mat[i][j] == 0:
seen = {mat[nr][nc] for nr, nc in FindNeighbor(i, j, N) if mat[nr][nc] > 1}
maxPathLen = max(maxPathLen, 1 + sum(maxPath[i] for i in seen))
return maxPathLen
I = [[1, 0], [0, 1]]
print("The length of largest path is " + str(findLargestPath(I))) আউটপুট
The length of largest path is 3
