ในเมทริกซ์ที่กำหนด มีสี่อ็อบเจ็กต์ที่จะวิเคราะห์ตำแหน่งขององค์ประกอบ:ซ้าย ขวา ล่าง และบน
การค้นหาแบบกว้างๆ ไม่ได้เป็นเพียงการค้นหาระยะทางที่สั้นที่สุดระหว่างสององค์ประกอบของเมทริกซ์ 2 มิติที่กำหนด ดังนั้นในแต่ละเซลล์ มีการดำเนินการสี่อย่างที่เราสามารถทำได้ ซึ่งสามารถแสดงเป็นตัวเลขสี่ตัวได้ เช่น
- '2' อธิบายว่าเซลล์ในเมทริกซ์คือต้นทาง
- '3' อธิบายว่าเซลล์ในเมทริกซ์คือปลายทาง
- '1' อธิบายว่าเซลล์สามารถย้ายไปในทิศทางอื่นได้
- '0' อธิบายว่าเซลล์ในเมทริกซ์ไม่สามารถเคลื่อนที่ไปในทิศทางใดๆ ได้
บนพื้นฐานของการให้เหตุผลของ Adobe เราสามารถดำเนินการค้นหาแบบกว้างก่อนบนเมทริกซ์ที่กำหนดได้
แนวทางในการแก้ปัญหานี้
อัลกอริทึมในการสำรวจเมทริกซ์ทั้งหมดและค้นหาระยะทางต่ำสุดหรือสั้นที่สุดระหว่างเซลล์ใดๆ โดยใช้ BFS มีดังนี้:
- ขั้นแรกให้ป้อนข้อมูลแถวและคอลัมน์
- เริ่มต้นเมทริกซ์ด้วยแถวและคอลัมน์ที่กำหนด
- ฟังก์ชันจำนวนเต็ม shortestDist(int row, int col, int mat[][col]) รับแถว คอลัมน์ และเมทริกซ์เป็นอินพุตและส่งกลับระยะทางที่สั้นที่สุดระหว่างองค์ประกอบของเมทริกซ์
- เริ่มต้นตัวแปรต้นทางและปลายทางเพื่อค้นหาต้นทางและองค์ประกอบปลายทาง
- หากองค์ประกอบเป็น '3' ให้ทำเครื่องหมายว่าเป็นปลายทาง และหากองค์ประกอบเป็น '2' ให้ทำเครื่องหมายว่าเป็นองค์ประกอบต้นทาง
- ตอนนี้ เริ่มต้นโครงสร้างข้อมูลคิวเพื่อใช้ Breadth First Search บนเมทริกซ์ที่กำหนด
- แทรกแถวและคอลัมน์ของเมทริกซ์ในคิวเป็นคู่ ตอนนี้ย้ายในเซลล์และดูว่าเป็นเซลล์ปลายทางหรือไม่ หากเซลล์ปลายทางมีระยะทางต่ำสุดหรือน้อยกว่าเซลล์ปัจจุบัน ให้อัปเดตระยะทาง
- ย้ายไปยังทิศทางอื่นอีกครั้งเพื่อค้นหาระยะห่างขั้นต่ำของเซลล์จากเซลล์ปัจจุบัน
- คืนระยะทางขั้นต่ำเป็นเอาต์พุต
ตัวอย่าง
#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;
} ผลลัพธ์
The Shortest Distance between Source and Destination is:4
