题目描述

给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 '0'), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固，所以墙不会被摧毁。

样例1

输入:
grid =[
     "0E00",
     "E0WE",
     "0E00"
]
输出: 3
解释:
把炸弹放在 (1,1) 能杀3个敌人

样例2

输入:
grid =[
     "0E00",
     "EEWE",
     "0E00"
]
输出: 2
解释:
P把炸弹放在 (0,0) 或 (0,3) 或 (2,0) 或 (2,3) 能杀2个敌人

算法

(DP) $O(nm)$

1. 预处理出每个点四个方向上能炸到的人数，下面以预处理左边能炸到的人数举例

2. 对于某一行，从左往右扫描，遇到墙则炸到的人数等于0，遇到敌人则等于左边相邻位置炸到的人数加1，若为空则等于左边相邻位置炸到的人数

3. 注意只能在空的地方放置炸弹，所以我们遍历每一个空点将四个方向上能炸到的人数相加，取最大值就是答案

C++ 代码

class Solution {
public:
    /**
     * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
     * @return: an integer, the maximum enemies you can kill using one bomb
     */
    int maxKilledEnemies(vector<vector<char>> &grid) {
        if (grid.size() == 0) return 0;

        int n = grid.size();
        int m = grid[0].size();

        int left[n + 1][m + 1], right[n + 1][m + 1], up[n + 1][m + 1], down[n + 1][m + 1];
        memset(left, 0, sizeof(left));
        memset(right, 0, sizeof(right));
        memset(up, 0, sizeof(up));
        memset(down, 0, sizeof(down));

        // left
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'W') {
                    left[i][j] = 0;
                    continue;
                }

                left[i][j] = grid[i][j] == 'E' ? 1 : 0;
                if (j > 0) left[i][j] += left[i][j - 1];
            }
        }

        // right
        for (int i = 0; i < n; i++) {
            for (int j = m - 1; j >= 0; j--) {
                if (grid[i][j] == 'W') {
                    right[i][j] = 0;
                    continue;
                }

                right[i][j] = grid[i][j] == 'E' ? 1 : 0;
                if (j < m - 1) right[i][j] += right[i][j + 1];
            }
        }

        // up
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'W') {
                    up[i][j] = 0;
                    continue;
                }

                up[i][j] = grid[i][j] == 'E' ? 1 : 0;
                if (i > 0) up[i][j] += up[i - 1][j];
            }
        }

        // down
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'W') {
                    down[i][j] = 0;
                    continue;
                }

                down[i][j] = grid[i][j] == 'E' ? 1 : 0;
                if (i < n - 1) down[i][j] += down[i + 1][j];
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(grid[i][j] == '0') {
                    res = max(res, left[i][j] + right[i][j] + up[i][j] + down[i][j]);
                }
            }
        }

        return res;
    }
};