ใน Matrix ที่กำหนด มี 4 ทิศทางวิเคราะห์ตำแหน่ง Element: Left, Right, Bottom, และ Top
Breadth First Search คือการหา Shortest Distance (ระยะทางสั้นที่สุด) ระหว่าง 2 Element ใน 2-D Matrix ที่กำหนด ในแต่ละ Cell มี 4 Operations ที่ทำได้ แสดงด้วยตัวเลข 4 ตัว:
- '2' หมายถึง Cell ใน Matrix เป็น Source (ต้นทาง)
- '3' หมายถึง Cell ใน Matrix เป็น Destination (ปลายทาง)
- '1' หมายถึง Cell สามารถเคลื่อนที่ต่อได้ในทิศทางนั้น
- '0' หมายถึง Cell ใน Matrix ไม่สามารถเคลื่อนที่ได้ในทิศทางใดๆ
จาก Justification ด้านบน เราสามารถทำ BFS Operation บน Matrix ที่กำหนดได้
แนวทางแก้ปัญหา
Algorithm สำหรับ Traverse ทั้ง Matrix และหา Minimum/Shortest Distance ระหว่าง Cell ใดๆ ด้วย BFS:
รับ Input Row และ Column
Initialize Matrix ด้วย Row และ Column ที่กำหนด
Integer Function shortestDist(int row, int col, int mat[][col]) รับ Row, Column, Matrix คืนค่า Shortest Distance ระหว่าง Element
Initialize Variable Source และ Destination เพื่อหา Source และ Destination Element
ถ้า Element เป็น '3' ทำเครื่องหมายเป็น Destination ถ้าเป็น '2' ทำเครื่องหมายเป็น Source
Initialize Queue Data Structure เพื่อ Implement BFS บน Matrix
Insert Row และ Column ของ Matrix ใน Queue เป็น Pair ตอนนี้ Move ใน Cell หาว่าเป็น Destination Cell หรือไม่ ถ้า Destination Cell มี Distance น้อยกว่า Current Cell ให้ Update Distance
Move ไปทิศทางอื่นเพื่อหา Minimum Distance ของ Cell จาก Current Cell
คืนค่า Minimum Distance เป็น Output
ตัวอย่าง
import queue
INF = 10000
class Node:
def __init__(self, i, j):
self.row_num = i
self.col_num = j
def findDistance(row, col, mat):
source_i = 0
source_j = 0
destination_i = 0
destination_j = 0
for i in range(0, row):
for j in range(0, col):
if mat[i][j] == 2:
source_i = i
source_j = j
if mat[i][j] == 3:
destination_i = i
destination_j = j
dist = []
for i in range(0, row):
sublist = []
for j in range(0, col):
sublist.append(INF)
dist.append(sublist)
# Initialise queue to start BFS on matrix
q = queue.Queue()
source = Node(source_i, source_j)
q.put(source)
dist[source_i][source_j] = 0
# Modified BFS by add constraint checks
while (not q.empty()):
# Extract and remove the node from the front of queue
temp = q.get()
x = temp.row_num
y = temp.col_num
# If move towards left is allowed or it is the destination cell
if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3):
# If distance to reach the cell to the left is less than the computed previous path distance, update it
if dist[x][y] + 1 < dist[x][y - 1]:
dist[x][y - 1] = dist[x][y] + 1
next = Node(x, y - 1)
q.put(next)
# If move towards right is allowed or it is the destination cell
if y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3):
if dist[x][y] + 1 < dist[x][y + 1]:
dist[x][y + 1] = dist[x][y] + 1
next = Node(x, y + 1)
q.put(next)
# If move towards up is allowed or it is the destination cell
if x - 1 >= 0 and (mat[x - 1][y] == 1 or mat[x-1][y] == 3):
if dist[x][y] + 1 < dist[x - 1][y]:
dist[x - 1][y] = dist[x][y] + 1
next = Node(x - 1, y)
q.put(next)
# If move towards down is allowed or it is the destination cell
if x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3):
if dist[x][y] + 1 < dist[x + 1][y]:
dist[x + 1][y] = dist[x][y] + 1
next = Node(x + 1, y)
q.put(next)
return dist[destination_i][destination_j]
row = 5
col = 5
mat = [
[1, 0, 0, 2, 1],
[1, 0, 2, 1, 1],
[0, 1, 1, 1, 0],
[3, 2, 0, 0, 1],
[3, 1, 0, 0, 1]
]
answer = findDistance(row, col, mat)
if answer == INF:
print("No Path Found")
else:
print("The Shortest Distance between Source and Destination is:")
print(answer)ผลลัพธ์
The Shortest Distance between Source and Destination is:
2