ตรวจสอบเส้นทางที่เป็นไปได้ในเมทริกซ์ 2 มิติใน C ++

พิจารณาว่าเรามีอาร์เรย์ 2 มิติ เราต้องค้นหาว่าเราจะหาเส้นทางจากมุมบนซ้ายไปมุมล่างขวาได้หรือไม่ เมทริกซ์เต็มไปด้วย 0 และ 1 0 หมายถึงพื้นที่เปิดโล่ง 1 หมายถึงการอุดตัน โปรดทราบว่ามุมบนซ้ายจะเป็น 1 เสมอ

สมมติว่าเมทริกซ์อยู่ด้านล่าง -

เส้นทางหนึ่งถูกทำเครื่องหมายเป็นสีเขียว มีเส้นทางอื่นด้วย ดังนั้นโปรแกรมจะคืนค่า จริง หากมีพาธ มิฉะนั้น จะเป็นเท็จ

เราจะแก้ปัญหานี้โดยเปลี่ยนโหนดที่เข้าถึงได้ทั้งหมดเป็น -1 ก่อนอื่นให้เปลี่ยนค่าของจุดเริ่มต้นเป็น -1 จากนั้นรับค่าถัดไปในแถวแรกและเปรียบเทียบกับค่าก่อนหน้าตั้งค่าปัจจุบันเท่ากับค่าก่อนหน้า ถ้ามันสามารถเข้าถึงได้ (ไม่ใช่ 0) ทำเช่นเดียวกันสำหรับค่าคอลัมน์ด้วย โดยเปรียบเทียบและตั้งค่าปัจจุบันกับค่าคอลัมน์ก่อนหน้าหากสามารถเข้าถึงได้ จากนั้นเริ่มจากแถวแรก คอลัมน์แรก แล้วหาค่าของแถวก่อนหน้า คอลัมน์ก่อนหน้า หาค่าต่ำสุดระหว่างแถวนั้น และตั้งค่าดัชนีปัจจุบันเป็นค่าต่ำสุด หากดัชนีปัจจุบันคือ 1 จะไม่มีการเปลี่ยนแปลง ในตอนท้ายหากดัชนีสุดท้ายเหมือนกับด้านล่างขวา ให้คืนค่า จริง ไม่เช่นนั้น เท็จ

ตัวอย่าง

#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