หาขั้นตอนน้อยที่สุดเพื่อไปถึงปลายแมทริกซ์ใน C++

สมมติว่ามีแมทริกซ์ 2D ที่มีจำนวนเต็มบวก เราต้องหาขั้นตอนน้อยที่สุดที่จำเป็นในการเคลื่อนที่ไปยังปลายของแมทริกซ์ (เซลล์ขวาล่างสุด) หากเราอยู่ที่เซลล์ (i, j) เราสามารถไปที่เซลล์ (i, j+mat[i, j]) หรือ (i+mat[i, j], j) เราไม่สามารถข้ามขอบเขตได้ ดังนั้นถ้าแมทริกซ์เป็นแบบด้านล่าง:

ผลลัพธ์จะเป็น 2 เส้นทางจะเป็น (0, 0) → (0, 2) → (2, 2)

ที่นี่เราจะใช้แนวทาง Dynamic Programming เพื่อแก้ปัญหานี้ สมมติว่าเราอยู่ที่เซลล์ (i, j) เราต้องการไปถึงเซลล์ (n-1, n-1) เราสามารถใช้ความสัมพันธ์แบบเรียกซ้ำได้ดังนี้:

DP[i, j] = 1 + min(DP[i+arr[i, j], j], DP[i, j+arr[i, j]])

ตัวอย่าง

#include <iostream> 
#define N 3 
using namespace std; 

int table[N][N];
bool temp_val[N][N];

int countSteps(int i, int j, int arr[][N]) {
    if (i == N - 1 && j == N - 1)
        return 0;
    if (i > N - 1 || j > N - 1)
        return INT_MAX;
    if (temp_val[i][j])
        return table[i][j];
    temp_val[i][j] = true;
    table[i][j] = 1 + min(countSteps(i + arr[i][j], j, arr), countSteps(i, j + arr[i][j], arr));
    return table[i][j];
}

int main() {
    int arr[N][N] = { { 2, 1, 2 }, { 1, 1, 1 }, { 1, 1, 1 } };
    int ans = countSteps(0, 0, arr);
    if (ans >= INT_MAX)
        cout << -1;
    else
        cout << "Number of steps: " << ans;
}

ผลลัพธ์

Number of steps: 2