ตรวจสอบ Path ใน 2D Matrix ใน C++

พิจารณา 2D Array ต้องการหาว่ามี Path จากมุมซ้ายบนไปมุมขวาล่างหรือไม่ Matrix ประกอบด้วย 0 และ 1 โดย 0 = พื้นที่ว่าง 1 = กีดขวาง จุดเริ่มต้นมุมซ้ายบนจะเป็น 1 เสมอ

ตัวอย่าง Matrix:

มี Path อยู่ (สีเขียว) โปรแกรมคืนค่า true ถ้ามี Path มิฉะนั้น false

วิธีแก้: เปลี่ยน Accessible Nodes เป็น -1 เริ่มจากจุดเริ่มต้น แล้วเผยแพร่ค่า -1 ไปทางขวาและลงตามเงื่อนไข ถ้าจุดปลายทางกลายเป็น -1 แสดงว่ามี Path

ตัวอย่างโค้ด C++

#include <iostream>
#define row 5
#define col 5
using namespace std;

bool isPathPresent(int arr[row][col]) {
    arr[0][0] = -1;
    for (int i = 1; i < row; i++)
        if (arr[i][0] != 1)
            arr[i][0] = arr[i - 1][0];
    for (int j = 1; j < col; j++)
        if (arr[0][j] != 1)
            arr[0][j] = arr[0][j - 1];
    for (int i = 1; i < row; i++)
        for (int j = 1; j < col; j++)
            if (arr[i][j] != 1)
                arr[i][j] = min(arr[i][j - 1], arr[i - 1][j]);
    return (arr[row - 1][col - 1] == -1);
}

int main() {
    int arr[row][col] = {{ 0, 0, 0, 1, 0},
                         {1, 0, 0, 1, 1},
                         { 0, 0, 0, 1, 0},
                         {1, 0, 0, 0, 0},
                         { 0, 0, 1, 0, 0}};
    if (isPathPresent(arr))
        cout << "Path is present";
    else
        cout << "No path has found";
}

ผลลัพธ์

Path is present