資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢帶有地雷路徑的最短安全路徑
在這個問題中，我們給定了一個矩陣 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
更新於: 2021-03-16
753 次檢視
廣告