পাইথনে বাইনারি ম্যাট্রিক্সে সর্বোচ্চ পথের দৈর্ঘ্য বের করা

বাইনারি ম্যাট্রিক্সে সর্বোচ্চ পথের দৈর্ঘ্য

এই সমস্যায়, আমাদের একটি বর্গ ম্যাট্রিক্স mat[][] দেওয়া আছে যার আকার m X n এবং প্রতিটি উপাদান হয় 0 অথবা 1। যদি কোনো উপাদানের মান 1 হয়, তাহলে সেটি কানেক্টেড, এবং যদি মান 0 হয়, তাহলে সেটি নট-কানেক্টেড। আমাদের কাজ হলো বাইনারি ম্যাট্রিক্সে সর্বোচ্চ পথের দৈর্ঘ্য বের করা।

সমস্যা বর্ণনা

সমস্যাটি সমাধান করতে হলে, আমাদের ম্যাট্রিক্সে সর্বোচ্চ দৈর্ঘ্যের পথ খুঁজে বের করতে হবে, অর্থাৎ ম্যাট্রিক্সের সব 1 উপাদান। পথ খুঁজার আগে, আমরা সর্বোচ্চ একটি 0 কে 1 এ রূপান্তর করব।

উদাহরণ

ইনপুট

mat[][] = {{1, 0}, {0, 1}}

আউটপুট

3

ব্যাখ্যা

আমরা (0, 1) বা (1, 0) ইনডেক্সের 0 কে রূপান্তর করে পথের দৈর্ঘ্য সর্বাধিক করতে পারি।

সমাধানের পদ্ধতি

সমস্যার একটি সহজ সমাধান হলো প্রতিটি 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("সর্বোচ্চ পথের দৈর্ঘ্য " + str(findLargestPath(I)))

আউটপুট

সর্বোচ্চ পথের দৈর্ঘ্য 3