用C++在有地雷的路径中找到最短的安全路线

2023-06-16 12:28:04 186

在这个问题中，我们得到一个矩阵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 
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<<"从源到目的地不可能有安全路径！";
   else
      cout<<"最短安全路径长度为 "<输出结果最短安全路径长度为 10
替代解决方案
该问题的另一种解决方案是使用广度优先搜索。使用队列，我们将找到从第一列到最后一列的路径，然后返回从第一列到最后一列的路径的最小距离。
程序来说明我们的解决方案的工作，
示例
#include 
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 distQueue;
   for(int i=0;i输出结果最短安全路径长度为 10

用C++在有地雷的路径中找到最短的安全路线

输入

解释

解决方法

示例

替代解决方案

示例

热门推荐

随机推荐