Trong bài toán này, chúng ta được đưa ra một ma trận [] []. Nó xác định một con đường có mìn được đánh dấu là 0. Nhiệm vụ của chúng tôi là Tìm đường đi an toàn ngắn nhất trong đường mòn có mìn.
Khi đi qua con đường an toàn, chúng ta cần tránh đi qua các ô liền kề của mìn (trái, phải, trên và dưới) vì không an toàn.
Tất cả các bước di chuyển hợp lệ khi đi qua con đường là -
- 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]
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
mat[][] = {
{1, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
} Đầu ra
length of shortest safe path is 7
Giải thích
{
{1, 1, 0, 1},
{1, 1, 0, 1},
{1, 1, 1, 1},
{1, 1, 1, 1}
} Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng backtracking. Nhưng trước khi tìm ra con đường dẫn đến giải pháp, chúng tôi sẽ đánh dấu tất cả các ô lân cận với alandmine là các ô không an toàn. Bây giờ, đối với các ô bắt đầu trong cột Đầu tiên, chúng ta sẽ đi đến từng ô an toàn từ vị trí đó và sau đó kiểm tra xem nó có dẫn đến vị trí thừa (bất kỳ ô nào trong cột cuối cùng) hay không. Sau đó, đối với tất cả các vị trí an toàn có thể dẫn đến đích, hãy tìm con đường ngắn nhất để đến đích. Nếu có thể, hãy trả về độ dài của con đường
Trả về -1, biểu thị không tìm thấy đường dẫn nào
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
Shortest Safe route Length is 10
Giải pháp thay thế
Một giải pháp thay thế cho vấn đề là sử dụng tìm kiếm đầu tiên theo chiều rộng. Sử dụng hàng đợi, chúng tôi sẽ tìm đường dẫn từ cột đầu tiên đến cột cuối cùng và sau đó trả về khoảng cách tối thiểu cho đường dẫn từ cột đầu tiên đến cột cuối cùng.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
Shortest Safe route Length is 10