สมมติว่าเรามีเมทริกซ์ที่มีตัวอักษร 'O' (พื้นที่ว่าง), 'G' (ผู้เฝ้าบัญชี), 'W' (กำแพง) ต้องการแทนที่ 'O' ทุกตัวด้วยระยะทางสั้นที่สุดจากผู้เฝ้าบัญชีใกล้ที่สุด (ไม่สามารถผ่านกำแพงได้) ในผลลัพธ์ G → 0, W → -1
ใช้ Multi-source BFS เริ่มจากทุก G พร้อมกัน
ตัวอย่างโค้ด Python
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.append((i, j, 0))
result[i][j] = 0
while q:
x, y, dist = q.popleft()
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.append((nx, ny, dist + 1))
for row in result:
print(' '.join(map(str, 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)
อินพุต
5x5 matrix with 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
