পাইথনে ব্যাঙ্ক ম্যাট্রিক্সে গার্ড থেকে ন্যূনতম দূরত্ব নির্ণয়

একটি ম্যাট্রিক্স দেওয়া আছে যেটে 'O' (খালি জায়গা), 'G' (গার্ড), 'W' (দেওয়াল) আছে। প্রতিটি 'O'-র সবচেয়ে নিকটতম 'G'-র দূরত্ব বের করতে হবে। দেওয়াল (W) দিয়ে যাওয়া যাবে না। আউটপুট ম্যাট্রিক্সে 'G' → 0, 'W' → -1, 'O' → ন্যূনতম দূরত্ব।

উদাহরণ

ইনপুট: [['O','O','O','O','G'], ['O','O','O','W','O'], ['O','W','O','O','O'], ['G','W','W','W','O'], ['O','O','O','O','G']]

আউটপুট: [[3,3,2,1,0], [2,3,3,-1,1], [1,-1,4,3,2], [0,-1,-1,-1,1], [1,2,2,1,0]]

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

1. মাল্টি-সোর্স BFS (Multi-source BFS) ব্যবহার করা হয়।
2. সকল গার্ড (G) কে শুরুতে কিউ (queue)তে ঢুকানো হয় distance 0 দিয়ে।
3. BFS চালিয়ে প্রতিটি খালি সেল (O)-র ন্যূনতম দূরত্ব আপডেট করা হয়।
4. দেওয়াল (W) কে -1 দিয়ে চিহ্নিত করা হয়।
5. ৪ দিক (আপ, ডাউন, লেফট, রাইট) এ যাওয়া সম্ভব।

পাইথন কোড

from collections import deque

M = 5
N = 5
dir_row = [-1, 0, 1, 0]
dir_col = [0, 1, 0, -1]

def is_ok(i, j):
    return 0 <= i < M and 0 <= j < N

def isSafe(i, j, matrix, result):
    return matrix[i][j] == 'O' and result[i][j] == -1

def calculate_dist(matrix):
    result = [[-1] * N for _ in range(M)]
    q = deque()
    
    for i in range(M):
        for j in range(N):
            if matrix[i][j] == 'G':
                q.appendleft([i, j, 0])
                result[i][j] = 0
    
    while q:
        curr = q.pop()
        x, y, dist = curr[0], curr[1], curr[2]
        for i in range(4):
            nx, ny = x + dir_row[i], y + dir_col[i]
            if is_ok(nx, ny) and isSafe(nx, ny, matrix, result):
                result[nx][ny] = dist + 1
                q.appendleft([nx, ny, dist + 1])
    
    for i in range(M):
        for j in range(N):
            print(result[i][j], end=" ")
        print()

matrix = [
    ['O', 'O', 'O', 'O', 'G'],
    ['O', 'O', 'O', 'W', 'O'],
    ['O', 'W', 'O', 'O', 'O'],
    ['G', 'W', 'W', 'W', 'O'],
    ['O', 'O', 'O', 'O', 'G']
]
calculate_dist(matrix)

ইনপুট

5x5 ম্যাট্রিক্স O, G, W দিয়ে

আউটপুট

3 3 2 1 0
2 3 3 -1 1
1 -1 4 3 2
0 -1 -1 -1 1
1 2 2 1 0