หาเส้นทางปลอดภัยที่สั้นที่สุดในเส้นทางที่มีระเบิดใน 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]

มาดูตัวอย่างเพื่อเข้าใจปัญหา

Input

mat[][] = { 
    {1, 1, 0, 1}, 
    {1, 1, 0, 1}, 
    {1, 1, 1, 1}, 
    {1, 1, 1, 1} 
}

Output

length of shortest safe path is 7

อธิบาย

{ 
    {1, 1, 0, 1}, 
    {1, 1, 0, 1}, 
    {1, 1, 1, 1}, 
    {1, 1, 1, 1} 
}

วิธีแก้ปัญหา

วิธีแก้ที่ง่ายคือใช้ backtracking แต่ก่อนหาเส้นทาง เราจะทำเครื่องหมายเซลล์ทั้งหมดที่อยู่ติดกับระเบิดเป็นเซลล์ไม่ปลอดภัย ตอนนี้ สำหรับเซลล์เริ่มต้นในคอลัมน์แรก เราจะไปที่เซลล์ที่ปลอดภัยจากตำแหน่งนั้น และตรวจสอบว่ามันนำไปสู่จุดหมาย (เซลล์ใดๆ ในคอลัมน์สุดท้าย) หรือไม่ แล้วสำหรับตำแหน่งปลอดภัยทั้งหมดที่สามารถนำไปสู่จุดหมาย ให้หาเส้นทางที่สั้นที่สุด ถ้าเป็นไปได้ คืนค่าความยาวเส้นทาง มิฉะนั้น คืนค่า -1 แทนไม่พบเส้นทาง

โปรแกรมแสดงการทำงานของวิธีแก้

ตัวอย่าง (Backtracking)

#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

วิธีแก้แบบอื่น (BFS)

วิธีแก้แบบอื่นคือใช้ breadth first search โดยใช้ queue เราจะหาเส้นทางจากคอลัมน์แรกไปคอลัมน์สุดท้าย แล้วคืนค่าระยะทางขั้นต่ำสำหรับเส้นทางจากคอลัมน์แรกไปคอลัมน์สุดท้าย

โปรแกรมแสดงการทำงานของวิธีแก้

ตัวอย่าง (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]){ 
    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