이 문제에서는 행렬 mat[][]가 주어집니다. 0으로 표시된 지뢰가 있는 경로를 정의합니다. 우리의 임무는 지뢰가 없는 경로에서 가장 안전한 최단 경로를 찾는 것입니다.
안전한 경로를 통과하는 동안 안전하지 않기 때문에 지뢰의 인접 셀(왼쪽, 오른쪽, 위, 아래)을 걷는 것을 피해야 합니다.
경로를 횡단하는 동안 모든 유효한 이동은 -
- Left : mat[i][j] => mat[i-1][j] - Right : mat[i][j] => mat[i+1][j] - Top : mat[i][j] => mat[i][j - 1] - Bottom : mat[i][j] => mat[i][j + 1]
문제를 이해하기 위해 예를 들어보겠습니다.
입력
mat[][] = {
{1, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
} 출력
length of shortest safe path is 7
설명
{
{1, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
} 솔루션 접근 방식
문제에 대한 간단한 해결책은 역추적을 사용하는 것입니다. 그러나 솔루션에 대한 경로를 찾기 전에 랜드민에 인접한 모든 세포를 안전하지 않은 세포로 표시합니다. 이제 첫 번째 열의 시작 셀에 대해 해당 위치에서 안전한 각 셀로 이동한 다음 대상(마지막 열의 모든 셀)으로 이어지는지 확인합니다. 그런 다음 목적지에 도달할 수 있는 모든 안전한 위치에 대해 목적지에 도달하는 최단 경로를 찾습니다. 가능하면 경로의 길이를 반환합니다.
그렇지 않으면 발견된 경로가 없음을 나타내는 -1을 반환합니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <bits/stdc++.h>
using namespace std;
#define R 11
#define C 10
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
bool isSafe(int mat[R][C], int isvisited[R][C], int x, int y){
if (mat[x][y] == 0 || isvisited[x][y])
return false;
return true;
}
bool isValid(int x, int y){
if (x < R && y < C && x >= 0 && y >= 0)
return true;
return false;
}
void unSafeCellsInPath(int mat[R][C]){
for (int i = 0; i < R; i++){
for (int j = 0; j < C; j++){
if (mat[i][j] == 0){
for (int k = 0; k < 4; k++)
if (isValid(i + rowNum[k], j + colNum[k]))
mat[i + rowNum[k]][j + colNum[k]] = -1;
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++){
if (mat[i][j] == -1)
mat[i][j] = 0;
}
}
}
void findShortestSafeRouteRec(int mat[R][C], int isvisited[R][C], int i, int j, int &min_dist, int dist){
if (j == C-1){
min_dist = min(dist, min_dist);
return;
}
if (dist > min_dist)
return;
isvisited[i][j] = 1;
for (int k = 0; k < 4; k++){
if (isValid(i + rowNum[k], j + colNum[k]) && isSafe(mat, isvisited, i + rowNum[k], j + colNum[k])){
findShortestSafeRouteRec(mat, isvisited, i + rowNum[k], j + colNum[k], min_dist, dist + 1);
}
}
isvisited[i][j] = 0;
}
int findShortestSafeRoute(int mat[R][C]){
int minSafeDist = INT_MAX;
int isvisited[R][C];
unSafeCellsInPath(mat);
for (int i = 0; i < R; i++) {
if (mat[i][0] == 1) {
memset(isvisited, 0, sizeof isvisited);
findShortestSafeRouteRec(mat, isvisited, i, 0, minSafeDist, 0);
if(minSafeDist == C - 1)
break;
}
}
if (minSafeDist != INT_MAX)
return minSafeDist;
else
return -1;
}
int main() {
int mat[R][C] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }
};
int pathLen = findShortestSafeRoute(mat);
if(pathLen == -1)
cout<<"No Safe Path from source to destination possible!";
else
cout<<"Shortest Safe route Length is "<<pathLen;
return 0;
} 출력
Shortest Safe route Length is 10
대체 솔루션
문제에 대한 대체 솔루션은 너비 우선 탐색을 사용하는 것입니다. 큐를 사용하여 첫 번째 열에서 마지막 열까지의 경로를 찾은 다음 첫 번째 열에서 마지막 열까지의 경로에 대한 최소 거리를 반환합니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <bits/stdc++.h>
using namespace std;
#define R 11
#define C 10
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
struct Key{
int x,y;
Key(int i,int j){ x=i;y=j;};
};
bool isValid(int x, int y) {
if (x < R && y < C && x >= 0 && y >= 0)
return true;
return false;
}
int findShortestSafeRoute(int mat[R][C]){
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (mat[i][j] == 0) {
for (int k = 0; k < 4; k++)
if (isValid(i + rowNum[k], j + colNum[k]))
mat[i + rowNum[k]][j + colNum[k]] = -1;
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (mat[i][j] == -1)
mat[i][j] = 0;
}
}
int visited[R][C];
for(int i=0;i<R;i++){
for(int j=0;j<C;j++)
visited[i][j] = -1;
}
queue<Key> distQueue;
for(int i=0;i<R;i++){
if(mat[i][0] == 1){
distQueue.push(Key(i,0));
visited[i][0] = 0;
}
}
while(!distQueue.empty()){
Key k = distQueue.front();
distQueue.pop();
int d = visited[k.x][k.y];
int x = k.x;
int y = k.y;
for (int k = 0; k < 4; k++) {
int xp = x + rowNum[k];
int yp = y + colNum[k];
if(isValid(xp,yp) && visited[xp][yp] == -1 && mat[xp][yp] == 1){
visited[xp][yp] = d+1;
distQueue.push(Key(xp,yp));
}
}
}
int pathLen = INT_MAX;
for(int i=0;i<R;i++){
if(mat[i][C-1] == 1 && visited[i][C-1] != -1){
pathLen = min(pathLen,visited[i][C-1]);
}
}
if(pathLen == INT_MAX)
return -1;
else
return pathLen;
}
int main() {
int mat[R][C] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }
};
int pathLen = findShortestSafeRoute(mat);
if(pathLen == -1)
cout<<"No Safe Path from source to destination possible!";
else
cout<<"Shortest Safe route Length is "<<pathLen;
return 0;
} 출력
Shortest Safe route Length is 10