পাইথনে সব ম্যানুসকে যেকোনো সেলে মিলাতে ন্যূনতম স্টেপ বের করা

মান লইয়া আমাদের একটি 2D ম্যাট্রিক্স আছে যেখানে এই ভ্যালুগুলো থাকে: 0 রিপ্রেজেন্ট করে খালি সেল। 1 রিপ্রেজেন্ট করে দেওয়াল। 2 রিপ্রেজেন্ট করে ম্যানুস। এখন একটি ম্যানুস চার দিকের যেকোনো দিকে (আপ, ডাউন, লেফট, রাইট) চলতে পারে অথবা একই জায়গায় থাকতে পারে এক টাইম ইউনিটে। আমাদের এমন একটি ওকবেল সেল খুঁজে বের করতে হবে যেটি সবার মিলানের জন্য টাইম মিনিমাইজ করে এবং সেই টাইম রিটার্ন করতে হবে। মনে রাখবেন দুজন ম্যানুস একই খালি সেল দিয়ে চলে যেতে পারে এবং যেকোনো দুজন ম্যানুসের মধ্যে পাথ আছে ধরে নেওয়া হয়েছে।

তবে, যদি ইনপুট হয়

2	1	0
1	0	2
2	2	0

তবে আউটপুট হবে 2, কারণ সবাই matrix[1, 1] পজিশনে সর্বোচ্চ ২ স্টেপে মিলতে পারেন।

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:

bfs() ফাংশন ডিফাইন করুন। এটি r, c নেবে
queue := একটি কিউ ডিফাইন করুন এবং (r, c) পেয়ার ইনসার্ট করুন
dist := একটি ম্যাপ key-value pair দিয়ে {(r, c) : 0}
queue-এ প্রতিটি (r, c) পেয়ারের জন্য:
- যদি dist[r, c] > 15 হয়, লুপ ব্রেক করুন
- (r, c)-এর প্রতিটি নেইবর (nr, nc) এর জন্য:
  - যদি (nr, nc) dist-এ না থাকে, তবে dist[nr, nc] := dist[r, c] + 1 এবং (nr, nc) queue-তে পুশ করুন
dist রিটার্ন করুন

মেইন মেথড থেকে:

dist := null
প্রতিটি রো নম্বর r এবং row এলিমেন্টের জন্য:
- প্রতিটি কলাম নম্বর c এবং row[c] ভ্যালু val এর জন্য:
  - যদি val == 2 হয়:
    - ndist := bfs(r, c)
    - যদি dist null হয়, dist := ndist
    - অন্যথায়, dist-এর প্রতিটি key-এর জন্য:
      - যদি key ndist-এ থাকে, dist[key] := max(dist[key], ndist[key])
      - অন্যথায় dist[key] ডিলিট করুন
dist খালি না হলে dist-এর সব ভ্যালুর মিনিমাম রিটার্ন করুন, অন্যথায় ০

উদাহরণ

class Solution:
    def solve(self, A):
        R, C = len(A), len(A[0])
        def get_neighbor(r, c):
            for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
                if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
                    yield nr, nc
        def bfs(r, c):
            queue = [(r, c)]
            dist = {(r, c): 0}
            for r, c in queue:
                if dist[r, c] > 15:
                    break
                for nr, nc in get_neighbor(r, c):
                    if (nr, nc) not in dist:
                        dist[nr, nc] = dist[r, c] + 1
                        queue.append((nr, nc))
            return dist
        dist = None
        for r, row in enumerate(A):
            for c, val in enumerate(row):
                if val == 2:
                    ndist = bfs(r, c)
                    if dist is None:
                        dist = ndist
                    else:
                        for key in list(dist.keys()):
                            if key in ndist:
                                dist[key] = max(dist[key], ndist[key])
                            else:
                                del dist[key]
        return min(dist.values()) if dist else 0

ob = Solution()
matrix = [
    [2, 0, 1, 0],
    [1, 0, 0, 2],
    [2, 0, 2, 0]
]
print(ob.solve(matrix))

ইনপুট

[ [2, 0, 1, 0], [1, 0, 0, 2], [2, 0, 2, 0] ]