Chương trình tìm số địch tối đa bị tiêu diệt bằng bom trong C++

Giới thiệu

Cho ma trận 2D với giá trị: 0 (ô trống), 1 (tường), 2 (kẻ thù). Đặt một bom tại ô trống (0). Bom tiêu diệt tất cả kẻ thù trên cùng hàng và cột cho đến khi gặp tường. Tìm số kẻ thù tối đa có thể tiêu diệt.

Ví dụ

Ma trận: {{0,2,0,0}, {2,0,1,2}, {0,2,0,0}} → Đặt bom tại (1,1) tiêu diệt 3 kẻ thù.

Ý tưởng giải thuật (Tiền xử lý hàng/cột)

1. Duyệt ma trận, tính trước số kẻ thù trên mỗi đoạn hàng/cột không bị tường chặn.
2. Dùng mảng colCnt[j] lưu số kẻ thù trên cột j từ hàng hiện tại xuống dưới cho đến tường.
3. Biến rowCnt lưu số kẻ thù trên hàng i từ cột hiện tại sang phải cho đến tường.
4. Khi ở ô trống (0), cập nhật kết quả = max(kết quả, rowCnt + colCnt[j]).

Ví dụ triển khai (C++)

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

class Solution {
public:
    int maxKilledEnemies(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;
        int n = grid.size(), m = grid[0].size();
        int maxKills = 0;
        int rowCnt = 0;
        vector<int> colCnt(m, 0);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // Tính rowCnt nếu ở đầu hàng hoặc sau tường
                if (j == 0 || grid[i][j-1] == 1) {
                    rowCnt = 0;
                    for (int k = j; k < m && grid[i][k] != 1; k++)
                        if (grid[i][k] == 2) rowCnt++;
                }
                
                // Tính colCnt[j] nếu ở đầu cột hoặc sau tường
                if (i == 0 || grid[i-1][j] == 1) {
                    colCnt[j] = 0;
                    for (int k = i; k < n && grid[k][j] != 1; k++)
                        if (grid[k][j] == 2) colCnt[j]++;
                }
                
                // Cập nhật kết quả tại ô trống
                if (grid[i][j] == 0)
                    maxKills = max(maxKills, rowCnt + colCnt[j]);
            }
        }
        return maxKills;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,2,0,0}, {2,0,1,2}, {0,2,0,0}};
    cout << ob.maxKilledEnemies(v); // 3
    return 0;
}

Đầu vào

{{0,2,0,0}, {2,0,1,2}, {0,2,0,0}}

Đầu ra

3