Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0'(the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.

Example

Example1

Input:
grid =[
     "0E00",
     "E0WE",
     "0E00"
]
Output: 3
Explanation:
Placing a bomb at (1,1) kills 3 enemies

Example2

Input:
grid =[
     "0E00",
     "EEWE",
     "0E00"
]
Output: 2
Explanation:
Placing a bomb at (0,0) or (0,3) or (2,0) or (2,3) kills 2 enemies

Notice

You can only put the bomb at an empty cell.

 

分析

这道题可以采用两个二维数组rowSum, colSum分别记录[i][j]位置所能分别消灭的该行和该列的敌人数。之后遍历grid，当grid[i][j] == '0'时，计算最大的rowSum[i][j] + colSum[i][j]的最大值。

Code

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) {
        // write your code here
        int rows = grid.size();
        if (rows == 0)
            return 0;
        
        int cols = grid[0].size();
        
        vector<vector<int>> rowSum(rows, vector<int>(cols, 0));
        vector<vector<int>> colSum(rows, vector<int>(cols, 0));
        for (int i = 0; i < rows; i ++)
        {
            int lasts = 0;
            int j = 0;
            int cum = 0;
            while (j < cols)
            {
                if (grid[i][j] != 'W')
                {
                    cum += grid[i][j] == 'E' ? 1:0;
                }
                else
                {
                    for (int k = lasts; k < j; k ++)
                    {
                        rowSum[i][k] = cum;
                    }
                    cum = 0;
                    lasts = j + 1;
                }
                j ++;
            }
            for (int k = lasts; k < j; k ++)
            {
                rowSum[i][k] = cum;
            }
        }
        
        for (int i = 0; i < cols; i ++)
        {
            int lasts = 0;
            int j = 0;
            int cum = 0;
            while (j < rows)
            {
                if (grid[j][i] != 'W')
                {
                    cum += grid[j][i] == 'E' ? 1:0;
                }
                else
                {
                    for (int k = lasts; k < j; k ++)
                    {
                        colSum[k][i] = cum;
                    }
                    cum = 0;
                    lasts = j + 1;
                }
                j ++;
            }
            for (int k = lasts; k < j; k ++)
            {
                colSum[k][i] = cum;
            }
        }
        
        int res = 0;
        for (int i = 0; i < rows; i ++)
        {
            for (int j = 0; j < cols; j ++)
            {
                if (grid[i][j] == '0')
                {
                    res = max(res, rowSum[i][j] + colSum[i][j]);
                }
            }
        }
        return res;
    }
};

运行效率

Your submission beats 93.20% Submissions!