পাইথনে ম্যাট্রিক্সে একটি সেল থেকে অন্য সেলে যেতে ন্যূনতম মুভ সংখ্যা

একটি N x N ম্যাট্রিক্স M দেওয়া আছে যেটি ১, ০, ২, ৩ দিয়ে ভরা। ১ = সোর্স (Source), ২ = ডেস্টিনেশন (Destination), ৩ = ব্ল্যাঙ্ক সেল (Blank cell), ০ = দেওয়াল (Wall)। শুধু ব্ল্যাঙ্ক সেল (৩) দিয়ে আপ, ডাউন, লেফট, রাইট-এ যাওয়া যায়। সোর্স থেকে ডেস্টিনেশন পর্যন্ত ন্যূনতম মুভ সংখ্যা বের করতে হবে।

উদাহরণ

ইনপুট ম্যাট্রিক্স:

ন্যূনতম মুভ = ৫ (হরেজ পথটি সবচেয়ে ছোট)।

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

1. প্রতিটি সেলকে একটি নোড (node) হিসেবে বিবেচনা করে একটি গ্রাফ তৈরি করা হয়।
2. সেলের মান ০ নয় এমন সেলগুলোকে নোড হিসেবে নেওয়া হয়।
3. সन्नিকট সেলগুলো (আপ, ডাউন, লেফট, রাইট) যেটি ০ নয়, তাদের মধ্যে এজ (edge) তৈরি করা হয়।
4. সোর্স (১) এবং ডেস্টিনেশন (২) সেলগুলো চিহ্নিত করা হয়।
5. BFS (Breadth-First Search) ব্যবহার করে সোর্স থেকে ডেস্টিনেশন পর্যন্ত ন্যূনতম পথ বের করা হয়।

পাইথন কোড

from collections import deque

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj = [[] for _ in range(nodes)]
    
    def insert_edge(self, src, dest):
        self.adj[src].append(dest)
        self.adj[dest].append(src)
    
    def BFS(self, src, dest):
        if src == dest:
            return 0
        level = [-1] * self.nodes
        q = deque()
        level[src] = 0
        q.append(src)
        
        while q:
            u = q.popleft()
            for v in self.adj[u]:
                if level[v] == -1:
                    level[v] = level[u] + 1
                    q.append(v)
        return level[dest]

def is_ok(i, j, mat, order):
    if i < 0 or i >= order or j < 0 or j >= order or mat[i][j] == 0:
        return False
    return True

def get_min_math(mat):
    order = len(mat)
    src = dest = None
    nodes = order * order + 2
    g = Graph(nodes)
    k = 1
    
    for i in range(order):
        for j in range(order):
            if mat[i][j] != 0:
                if is_ok(i, j + 1, mat, order):
                    g.insert_edge(k, k + 1)
                if is_ok(i, j - 1, mat, order):
                    g.insert_edge(k, k - 1)
                if j < order - 1 and is_ok(i + 1, j, mat, order):
                    g.insert_edge(k, k + order)
                if i > 0 and is_ok(i - 1, j, mat, order):
                    g.insert_edge(k, k - order)
                
                if mat[i][j] == 1:
                    src = k
                if mat[i][j] == 2:
                    dest = k
                k += 1
    
    return g.BFS(src, dest)

order = 4
mat = [[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]
print(get_min_math(mat))

ইনপুট

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

আউটপুট

5