ในเมทริกซ์ที่กำหนด มีสี่อ็อบเจ็กต์ที่จะวิเคราะห์ตำแหน่งขององค์ประกอบ:ซ้าย ขวา ล่าง และบน
การค้นหาแบบกว้างๆ ไม่ได้เป็นเพียงการค้นหาระยะทางที่สั้นที่สุดระหว่างสององค์ประกอบของเมทริกซ์ 2 มิติที่กำหนด ดังนั้น ในแต่ละเซลล์ มีการดำเนินการสี่อย่างที่เราสามารถทำได้ ซึ่งสามารถแสดงเป็นตัวเลขสี่ตัว เช่น
- '2' อธิบายว่าเซลล์ในเมทริกซ์คือต้นทาง
- '3' อธิบายว่าเซลล์ในเมทริกซ์คือปลายทาง
- '1' อธิบายว่าเซลล์สามารถย้ายไปในทิศทางอื่นได้
- '0' อธิบายว่าเซลล์ในเมทริกซ์ไม่สามารถเคลื่อนที่ไปในทิศทางใดๆ ได้
บนพื้นฐานของการให้เหตุผลของ Adobe เราสามารถดำเนินการค้นหาแบบกว้างก่อนบนเมทริกซ์ที่กำหนดได้
แนวทางในการแก้ปัญหานี้
อัลกอริทึมในการสำรวจเมทริกซ์ทั้งหมดและค้นหาระยะทางต่ำสุดหรือสั้นที่สุดระหว่างเซลล์ใดๆ โดยใช้ BFS มีดังนี้:
- ขั้นแรกให้ป้อนข้อมูลของแถวและคอลัมน์
- เริ่มต้นเมทริกซ์ด้วยแถวและคอลัมน์ที่กำหนด
- ฟังก์ชันจำนวนเต็ม shortestDist(int row, int col, int mat[][col]) รับแถว คอลัมน์ และเมทริกซ์เป็นอินพุตและส่งกลับระยะทางที่สั้นที่สุดระหว่างองค์ประกอบของเมทริกซ์
- เริ่มต้นตัวแปรต้นทางและปลายทางเพื่อค้นหาต้นทางและองค์ประกอบปลายทาง
- หากองค์ประกอบเป็น '3' ให้ทำเครื่องหมายว่าเป็นปลายทาง และหากองค์ประกอบเป็น '2' ให้ทำเครื่องหมายว่าเป็นองค์ประกอบต้นทาง
- ตอนนี้ เริ่มต้นโครงสร้างข้อมูลคิวเพื่อใช้ Breadth First Search บนเมทริกซ์ที่กำหนด
- แทรกแถวและคอลัมน์ของเมทริกซ์ในคิวเป็นคู่ ตอนนี้ย้ายในเซลล์และดูว่าเป็นเซลล์ปลายทางหรือไม่ หากเซลล์ปลายทางมีระยะทางต่ำสุดหรือน้อยกว่าเซลล์ปัจจุบัน ให้อัปเดตระยะทาง
- ย้ายไปยังทิศทางอื่นอีกครั้งเพื่อค้นหาระยะห่างขั้นต่ำของเซลล์จากเซลล์ปัจจุบัน
- คืนระยะทางขั้นต่ำเป็นเอาต์พุต
ตัวอย่าง
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 destnation 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 distance to reach the cell to the right 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 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 distance to reach the cell to the up is less than the computed previous path distance, update it
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 distance to reach the cell to the down is less than the computed previous path distance, update it
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
