ในเมทริกซ์ที่กำหนด มีสี่อ็อบเจ็กต์ที่จะวิเคราะห์ตำแหน่งขององค์ประกอบ:ซ้าย ขวา ล่าง และบน
การค้นหาแบบกว้างๆ ไม่ได้เป็นเพียงการค้นหาระยะทางที่สั้นที่สุดระหว่างสององค์ประกอบของเมทริกซ์ 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