Trong một ma trận nhất định, có bốn đối tượng để phân tích vị trí của phần tử:trái, phải, dưới cùng và trên cùng.
Breadth First Search không có gì khác ngoài việc tìm khoảng cách ngắn nhất giữa hai phần tử của Ma trận 2-D cho trước. Do đó, trong mỗi ô, chúng ta có thể thực hiện bốn phép toán mà chúng ta có thể thực hiện bằng bốn chữ số, chẳng hạn như,
- '2' mô tả rằng ô trong ma trận là Nguồn.
- '3' mô tả rằng ô trong ma trận là Đích.
- '1' mô tả rằng ô có thể được di chuyển xa hơn theo một hướng.
- '0' mô tả rằng không thể di chuyển ô trong ma trận theo bất kỳ hướng nào.
Trên cơ sở biện minh của adobe, chúng tôi có thể thực hiện Thao tác tìm kiếm đầu tiên theo chiều rộng trên một Ma trận nhất định.
Phương pháp tiếp cận để giải quyết vấn đề này
Thuật toán duyệt toàn bộ ma trận và tìm khoảng cách nhỏ nhất hoặc ngắn nhất giữa bất kỳ ô nào bằng BFS như sau:
- Đầu tiên, hãy lấy đầu vào của hàng và cột.
- Khởi tạo ma trận với hàng và cột đã cho.
- Một hàm số nguyên shortDist (int row, int col, int mat [] [col]) lấy hàng, cột và ma trận làm đầu vào và trả về khoảng cách ngắn nhất giữa các phần tử của ma trận.
- Khởi tạo nguồn và đích của biến để tìm ra nguồn cũng như phần tử đích.
- Nếu phần tử là "3", hãy đánh dấu phần tử đó là đích và nếu phần tử là "2", hãy đánh dấu phần tử đó là phần tử nguồn.
- Bây giờ hãy khởi tạo cấu trúc dữ liệu hàng đợi để triển khai Tìm kiếm đầu tiên theo chiều rộng trên ma trận đã cho.
- Chèn hàng và cột của ma trận vào hàng đợi dưới dạng các cặp. Bây giờ di chuyển trong ô và tìm xem nó có phải là ô đích hay không. Nếu ô đích có khoảng cách tối thiểu hoặc nhỏ hơn ô hiện tại, thì hãy cập nhật khoảng cách.
- Một lần nữa di chuyển sang một hướng khác để tìm ra khoảng cách tối thiểu của ô tính từ ô hiện tại.
- Trả lại khoảng cách tối thiểu làm đầu ra.
Ví dụ
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) Đầu ra
The Shortest Distance between Source and Destination is:2