LeetCode 361. 轰炸敌人（前缀和DP）

'W' 表示一堵墙
'E' 表示一个敌人
'0'（数字 0）表示一个空位

示例:

输入: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
输出: 3 
解释: 对于如下网格

0 E 0 0 
E 0 W E 
0 E 0 0

假如在位置 (1,1) 放置炸弹的话，可以炸到 3 个敌人

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
    	if(grid.empty() || grid[0].empty())
    		return 0;
    	int m = grid.size(), n = grid[0].size(), i, j, pre = 0;
    	vector<vector<int>> ans(m, vector<int>(n,0));
    	//分四个方向求前缀和
    	for(i = 0; i < m; ++i)
    		for(j = 0, pre=0; j < n; ++j)
    		{
    			if(grid[i][j] =='W')
    				pre = 0;
    			else if(grid[i][j] =='E')
    				pre++;
    			else
    				ans[i][j] += pre;
    		}
    	for(i = 0; i < m; ++i)
    		for(j = n-1, pre=0; j >= 0; --j)
    		{
    			if(grid[i][j] =='W')
    				pre = 0;
    			else if(grid[i][j] =='E')
    				pre++;
    			else
    				ans[i][j] += pre;
    		}
    	for(j = 0; j < n; ++j)
    		for(i = 0, pre=0; i < m; ++i)
    		{
    			if(grid[i][j] =='W')
    				pre = 0;
    			else if(grid[i][j] =='E')
    				pre++;
    			else
    				ans[i][j] += pre;
    		}
    	for(j = 0; j < n; ++j)
    		for(i = m-1, pre=0; i >= 0; --i)
    		{
    			if(grid[i][j] =='W')
    				pre = 0;
    			else if(grid[i][j] =='E')
    				pre++;
    			else
    				ans[i][j] += pre;
    		}
    	int maxcount = 0;
    	for(i = 0; i < m; ++i)
    		for(j = 0; j < n; ++j)
    			maxcount = max(maxcount, ans[i][j]);
		return maxcount;
    }
};