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. Vì vậy, 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 hàng và cột đầu vào.
- 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ụ
#include<bits/stdc++.h>
using namespace std;
int findDistance(int row, int col, int mat[][5]) {
int source_i, source_j, destination_i, destination_j;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mat[i][j] == 2) {
source_i = i;
source_j = j;
}
if (mat[i][j] == 3) {
destination_i = i;
destination_j = j;
}
}
}
int dist[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++)
dist[i][j] = INT_MAX;
}
// initialise queue to start BFS on matrix
queue < pair < int, int >> q;
q.push(make_pair(source_i, source_j));
dist[source_i][source_j] = 0;
// modified BFS by add constraint checks
while (!q.empty()) {
// storing the x co-ordinate or row information of cell
int x = q.front().first;
// storing the y co-ordinate or column information of cell
int y = q.front().second;
// Remove the cell from queue
q.pop();
// If move towards left is allowed or it is the destnation cell
if (y - 1 >= 0 && (mat[x][y - 1] == 1 || 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;
q.push(mkp(x, y - 1));
}
}
// If move towards right is allowed or it is the destination cell
if (y + 1 < col && (mat[x][y + 1] == 1 || 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;
q.push(mkp(x, y + 1));
}
}
// If upward direction is allowed
if (x - 1 >= 0 && (mat[x - 1][y] == 1 || mat[x - 1][y] == 3)) {
if (dist[x][y] + 1 < dist[x - 1][y]) {
dist[x - 1][y] = dist[x][y] + 1;
q.push(mkp(x - 1, y));
}
}
// If downward direction allowed
if (x + 1 < row && (mat[x + 1][y] == 1 || 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;
q.push(mkp(x + 1, y));
}
}
}
return dist[destination_i][destination_j];
}
int main() {
// initialising number of rows and columns
int row = 5;
int col = 5;
// initialising matrix
int mat[][5] = {
{1, 0, 0, 2, 1},
{1, 0, 1, 1, 1},
{0, 1, 1, 2, 0},
{3, 1, 0, 0, 1},
{1, 1, 0, 0, 1}
};
int answer = findDistance(row, col, mat);
// When source and destination are unreachable
if (answer == INT_MAX)
cout << "No Path Found" << endl;
else {
cout << "The Shortest Distance between Source and Destination is:" << endl;
cout << answer << endl;
}
return 0;
} Đầu ra
The Shortest Distance between Source and Destination is:4