Tìm đường đi an toàn ngắn nhất trong ma trận có mìn trong C++

Trong bài toán này, cho ma trận mat[][] định nghĩa đường đi có mìn (đánh dấu 0). Nhiệm vụ là tìm đường đi an toàn ngắn nhất.

Khi di chuyển, cần tránh các ô lân cận mìn (trái, phải, trên, dưới) vì không an toàn.

Các nước đi hợp 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]

Ví dụ minh họa:

Đầ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 giải

Dùng backtracking. Trước hết đánh dấu ô lân cận mìn là unsafe. Từ các ô an toàn cột đầu, thử đi đến cột cuối. Tìm đường ngắn nhất. Nếu không có đường, trả về -1.

Chương trình minh họa (Backtracking):

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] = { ... }; 
    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; 
}

Kết quả

Shortest Safe route Length is 10

Giải pháp thay thế (BFS): Dùng queue tìm đường từ cột đầu đến cột cuối, trả về khoảng cách nhỏ nhất.

Ví dụ (BFS)

#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]){ 
    // Đánh dấu unsafe cells 
    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, y = k.y; 
        for (int k = 0; k < 4; k++) { 
            int xp = x + rowNum[k], 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] = { ... }; 
    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; 
}

Kết quả

Shortest Safe route Length is 10