Bomb Enemy - Đặt bom tiêu diệt tối đa kẻ địch trong lưới

Cho lưới 2D: 'W' (tường), 'E' (kẻ địch), '0' (ô trống). Bom tiêu diệt tất cả kẻ địch cùng hàng và cột cho đến khi gặp tường. Chỉ được đặt bom trên ô trống. Tìm số kẻ địch tối đa có thể tiêu diệt bằng một bom.

Ví dụ: lưới 3x4 → kết quả 3 (đặt tại vị trí xanh).

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

Duyệt từng ô. Với mỗi hàng, khi gặp đầu hàng hoặc tường, đếm số 'E' đến tường tiếp theo → rowCnt. Tương tự cho cột → colCnt[j]. Nếu ô hiện tại là '0', cập nhật kết quả = max(kết quả, rowCnt + colCnt[j]). Độ phức tạp O(n*m).

Cài đặt C++

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

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int ret = 0;
        int n = grid.size();
        int m = n ? grid[0].size() : 0;
        int rowCnt = 0;
        vector<int> colCnt(m, 0);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // Xử lý hàng
                if (j == 0 || grid[i][j] == 'W') {
                    rowCnt = 0;
                    int k = (grid[i][j] == 'W') ? j + 1 : j;
                    for (; k < m && grid[i][k] != 'W'; k++)
                        rowCnt += (grid[i][k] == 'E');
                }
                // Xử lý cột
                if (i == 0 || grid[i][j] == 'W') {
                    colCnt[j] = 0;
                    int k = (grid[i][j] == 'W') ? i + 1 : i;
                    for (; k < n && grid[k][j] != 'W'; k++)
                        colCnt[j] += (grid[k][j] == 'E');
                }
                // Cập nhật kết quả
                if (grid[i][j] == '0')
                    ret = max(ret, rowCnt + colCnt[j]);
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<vector<char>> v = {{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}};
    cout << ob.maxKilledEnemies(v);
    return 0;
}

Đầu vào

{{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}}

Đầu ra

3