โปรแกรม C++ หาจำนวนการเปลี่ยนเซลล์น้อยที่สุดเพื่อเดินทางในกริด

กริด x×y มี # (บล็อก) และ . (ทาง) เริ่ม (0,0) ถึง (x-1,y-1) เดินได้เฉพาะขวาและลง ต้องการหาจำนวนเซลล์ # น้อยที่สุดที่ต้องเปลี่ยนเป็น . เพื่อให้มีทางถึงปลายทาง (จุดเริ่มและปลายเป็น . แน่นอน)

ตัวอย่าง: x=4,y=4, grid={"..#.", "#.#.", "#.##", "###."} ผลลัพธ์: 1 (เปลี่ยน (2,2) เป็นทาง)

ขั้นตอนการแก้ปัญหา (DP บนกริด)

1. สร้าง mat[x][y] เริ่มต้นค่ามาก (100)
2. mat[0][0] = (grid[0][0]=='#') ? 1 : 0
3. DP: สำหรับทุก (i,j) อัปเดตขวาและลง:
   • mat[i+1][j] = min(mat[i+1][j], mat[i][j] + (grid[i+1][j]=='#' && grid[i][j]=='.'))
   • mat[i][j+1] = min(mat[i][j+1], mat[i][j] + (grid[i][j+1]=='#' && grid[i][j]=='.'))
4. คืน mat[x-1][y-1]

เงื่อนไข grid[next]=='#' && grid[curr]=='.' หมายถึง "เปลี่ยนจากบล็อกเป็นทางเมื่อมาจากทาง"

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

#include <bits/stdc++.h>
using namespace std;

int solve(int x, int y, vector<string> grid) {
    vector<vector<int>> mat(x, vector<int>(y, 100));
    mat[0][0] = (grid[0][0] == '#') ? 1 : 0;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (i + 1 < x)
                mat[i+1][j] = min(mat[i+1][j], mat[i][j] + (grid[i+1][j]=='#' && grid[i][j]=='.'));
            if (j + 1 < y)
                mat[i][j+1] = min(mat[i][j+1], mat[i][j] + (grid[i][j+1]=='#' && grid[i][j]=='.'));
        }
    }
    return mat[x-1][y-1];
}

int main() {
    int x = 4, y = 4;
    vector<string> grid = {"..#.", "#.#.", "#.##", "###."};
    cout << solve(x, y, grid);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, 4, {"..#.", "#.#.", "#.##", "###."}

Output: 1