주어진 행렬에는 요소 위치를 분석하기 위한 4개의 개체가 있습니다:왼쪽, 오른쪽, 아래쪽 및 위쪽.
너비 우선 탐색은 주어진 2차원 행렬의 두 요소 사이의 최단 거리를 찾는 것뿐입니다. 따라서 각 셀에는 다음과 같이 4개의 숫자로 표현할 수 있는 4개의 연산이 있습니다.
- '2'는 행렬의 셀이 소스임을 나타냅니다.
- '3'은 행렬의 셀이 대상임을 나타냅니다.
- '1'은 셀이 한 방향으로 더 이동할 수 있음을 나타냅니다.
- '0'은 행렬의 셀이 어떤 방향으로도 이동할 수 없음을 나타냅니다.
어도비 정당화를 기반으로 주어진 매트릭스에 대해 너비 우선 검색 작업을 수행할 수 있습니다.
이 문제를 해결하기 위한 접근 방식
전체 행렬을 순회하고 BFS를 사용하여 셀 사이의 최소 또는 최단 거리를 찾는 알고리즘은 다음과 같습니다.
- 먼저 행과 열을 입력합니다.
- 주어진 행과 열로 행렬을 초기화합니다.
- 정수 함수 shortestDist(int row, int col, int mat[][col])은 행, 열 및 행렬을 입력으로 사용하고 행렬 요소 간의 최단 거리를 반환합니다.
- 변수 소스 및 대상을 초기화하여 소스 및 대상 요소를 찾습니다.
- 요소가 '3'이면 대상 요소로 표시하고 요소가 '2'이면 소스 요소로 표시합니다.
- 이제 주어진 행렬에서 너비 우선 검색을 구현하기 위해 대기열 데이터 구조를 초기화합니다.
- 큐에 있는 행렬의 행과 열을 쌍으로 삽입합니다. 이제 셀로 이동하여 대상 셀인지 아닌지 확인하십시오. 대상 셀의 거리가 최소값이거나 현재 셀보다 작으면 거리를 업데이트합니다.
- 다시 다른 방향으로 이동하여 현재 셀에서 셀의 최소 거리를 찾습니다.
- 최소 거리를 출력으로 반환합니다.
예시
#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