361. Bomb Enemy

做题历程：

1. 2016/Oct/12，本题应该是第一次做，大概耗时29分钟，独立解出

本题应该算是dynamic programming。难度尚可，不过解法不是很好表述，代码会更清晰。。就说一下核心的想法：

• 一个点可以炸的敌人数 = 向左可以炸的 + 向右可以炸的 + 向上可以炸的 + 向下可以炸的
• 乍看上一句是废话，其实不是，这简化的遍历的步骤，每次遍历只需要数一个方向的可以炸的数目，而不需要考虑另一侧的
• 代码很长，但是东西并不多，说白了，就是一次二重for loop求横向，一次二重 for loop求纵向，最后一次二重 for loop取和，并求最大值

代码如下：

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }
        int h = grid.size();
        int w = grid[0].size();
        vector<vector<int>> dp(h, vector<int>(w, 0));

        for (int i = 0; i < h; ++i) {
            int left = 0; 
            int right = 0;
            for (int j = 0; j < w; ++j) {
                if (grid[i][j] == 'E') {
                    left += 1;
                }
                else if (grid[i][j] == 'W') {
                    left = 0;
                }
                else {
                    dp[i][j] += left;
                }

                if (grid[i][w-1-j] == 'E') {
                    right += 1;
                }
                else if (grid[i][w-1-j] == 'W') {
                    right = 0;
                }
                else {
                    dp[i][w-1-j] += right;
                }
            }
        }

        for (int j = 0; j < w; ++j) {
            int up = 0;
            int down = 0;
            for (int i = 0; i < h; ++i) {
                if (grid[i][j] == 'E') {
                    down += 1;
                }
                else if (grid[i][j] == 'W') {
                    down = 0;
                }
                else {
                    dp[i][j] += down;
                }

                if (grid[h-1-i][j] == 'E') {
                    up += 1;
                }
                else if (grid[h-1-i][j] == 'W') {
                    up = 0;
                }
                else {
                    dp[h-1-i][j] += up;
                }
            }
        }
        int max_val = 0;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                max_val = max(max_val, dp[i][j]);
            }
        }
        return max_val;
    }
};