โปรแกรม C++ หาจำนวนครั้งตีน้อยที่สุดเพื่อสร้างทางไปตลาด

คำอธิบายปัญหา

สมมติว่าเรามีเมทริกซ์ H แถว W คอลัมน์ เซลล์เป็น '.' หรือ '#' จุด '.' คือทางเดิน '#' คือกำแพง อมลเดินจากบ้านมุมซ้ายบนไปตลาดมุมขวาล่าง เดินได้ 4 ทิศทาง ไม่ออกนอกเมือง ไม่เข้ากำแพง แต่มีแรงตีทำลายกำแพงในพื้นที่ 2x2 ได้ 1 ครั้ง ทำให้ทางเดินได้ ต้องการหาจำนวนครั้งตีน้อยที่สุดถึงตลาด

ตัวอย่าง: กริด 5x5 ตามตาราง ผลลัพธ์คือ 1 เพราะทำลายพื้นที่ 2x2 ที่ทำเครื่องหมาย ได้ทางไปตลาด

ขั้นตอนการแก้ปัญหา

n := จำนวนแถวของเมทริกซ์
m := จำนวนคอลัมน์ของเมทริกซ์
กำหนดอาร์เรย์ 2D dist ขนาด (n+1) x (m+1)
กำหนด deque dq
ใส่ (0,0) หน้าของ dq
dist[0,0] := 0
while dq ไม่ว่าง:
    v := ตัวหน้าของ dq
    ลบตัวหน้าออกจาก dq
    สำหรับ i := 0 ถึง 3:
        x := dx[i] + v[0]
        y := dy[i] + v[1]
        ถ้า x,y ในขอบเขต:
            ถ้า matrix[x,y] == '.':
                ถ้า dist[x,y] > dist[v[0],v[1]]:
                    dist[x,y] := dist[v[0],v[1]]
                    ใส่ {x,y} หน้าของ dq
            มิฉะนั้น:
                สำหรับ p := x-1 ถึง x+1:
                    สำหรับ q := y-1 ถึง y+1:
                        ถ้า p,q ในขอบเขต:
                            ถ้า dist[p,q] > dist[v[0],v[1]] + 1:
                                dist[p,q] := dist[v[0],v[1]] + 1
                                ใส่ {p,q} ท้ายของ dq
คืนค่า dist[n-1,m-1]

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

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

int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int solve(vector<vector<char>> matrix){
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9));
    deque<array<int, 2>> dq;
    dq.push_front({ 0, 0 });
    dist[0][0] = 0;
    while (!dq.empty()){
        auto v = dq.front();
        dq.pop_front();
        for (int i = 0; i < 4; i++){
            int x = dx[i] + v[0], y = dy[i] + v[1];
            if (x >= 0 && x < n && y >= 0 && y < m){
                if (matrix[x][y] == '.'){
                    if (dist[x][y] > dist[v[0]][v[1]]){
                        dist[x][y] = dist[v[0]][v[1]];
                        dq.push_front({ x, y });
                    }
                } else{
                    for (int p = x - 1; p <= x + 1; p++){
                        for (int q = y - 1; q <= y + 1; q++){
                            if (p >= 0 && p < n && q >= 0 && q < m){
                                if (dist[p][q] > dist[v[0]][v[1]] + 1){
                                    dist[p][q] = dist[v[0]][v[1]] + 1;
                                    dq.push_back({ p, q });
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return dist[n - 1][m - 1];
}

int main(){
    vector<vector<char>> matrix = { { '.', '.', '#', '.', '.' },
                                     { '#', '.', '#', '.', '#' },
                                     { '#', '#', '.', '#', '#' },
                                     { '#', '.', '#', '.', '#' },
                                     { '.', '.', '#', '.', '.' } };
    cout << solve(matrix) << endl;
}

อินพุต

{ { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } }

เอาต์พุต

1