Chương trình C++ tìm số cú đấm tối thiểu để đi từ góc trái trên đến góc phải dưới

Lưới H x W, ô '.' (đi được) hoặc '#' (chặn). Từ (0,0) đến (H-1,W-1), đi 4 hướng. Có thể dùng cú đấm phá vỡ vùng 2x2 (biến '#' thành '.'). Tìm số cú đấm tối thiểu.

Ví dụ

Lưới 5x5 (xem hình), đầu ra 1. Phá vùng 2x2 tại (1,2)-(2,3) tạo đường đi.

Giải thuật

0-1 BFS trên trạng thái (ô). Từ ô hiện tại, đi sang ô '.' chi phí 0 (push front). Gặp '#', thử phá 2x2 quanh nó: các ô trong 2x2 chi phí +1 (push back). Dùng deque, mảng dist lưu chi phí tối thiểu.

Mã 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;
}

Đầu vào / Đầu ra

Input: lưới 5x5 như mô tả
Output: 1