Tìm khoảng cách ngắn nhất từ vệ sĩ trong ngân hàng trong Python

Cho ma trận ký tự 'O' (không gian), 'G' (vệ sĩ), 'W' (tường). Thay mỗi 'O' bằng khoảng cách ngắn nhất đến một vệ sĩ (không đi qua tường). Vệ sĩ → 0, tường → -1.

Ví dụ ma trận 5x5 cho trước → ma trận kết quả với khoảng cách.

Giải thuật (BFS đa nguồn)

• Khởi tạo hàng đợi với tất cả vị trí 'G', khoảng cách 0.
• BFS: lấy vị trí hiện tại, thử 4 hướng.
• Nếu ô hợp lệ (trong phạm vi, là 'O', chưa gán khoảng cách) → gán dist+1, thêm vào hàng đợi.
• Kết thúc: ma trận result chứa khoảng cách, -1 cho tường và ô không đạt được.

Ví dụ

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:
        x, y, dist = q.pop()
        for d in range(4):
            nx, ny = x + dir_row[d], y + dir_col[d]
            if is_ok(nx, ny) and isSafe(nx, ny, matrix, result):
                result[nx][ny] = dist + 1
                q.appendleft([nx, ny, dist + 1])
    for row in result:
        print(' '.join(str(v) for v in row))

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)

Đầu vào

5x5 matrix with O, G, W

Đầu ra

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