描述

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

样例

给一个矩阵:

0 E 0 0E 0 W E0 E 0 0

返回 3.(在（1, 1）处放炸弹可以杀死 3 个敌人)

 

思路：很简单就能有思路，在每个空闲的点往上下左右搜索就可以了，不过考虑到可能进行的重复搜索，这种显而易见的解法效率并不高，时间复杂度约为O(mn(m+n))

　　　我的做法是通过一个cache矩阵存储中间信息，从上下左右四个方向往中间扫描，累加能够炸死的Enemy，差不多就是空间换时间的想法吧。时间复杂度应该是O(mn)。

　　   下面附上AC代码：

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
         
          
           > &grid) {        // write your code here        int height = grid.size();        if(!height) return 0;        int width = grid[0].size();        if(!width) return 0;                vector
           
            
             > cache(height,vector
             
              (width,0));        for(int y = 0; y < height; ++y){　　　　//左右方向enemy计数            int temp1 = 0;            int temp2 = 0;            for(int x = 0;x < width; ++x){                                if(grid[y][x] == 'E') ++temp1;　　　　　　//具体这个方向上的enemy计算只需简单判断一下就可以了                else if(grid[y][x] == '0') cache[y][x] += temp1;                else temp1 = 0;                                if(grid[y][width - x - 1] == 'E') ++temp2;                else if(grid[y][width - x - 1] == '0') cache[y][width - x - 1] += temp2;                else temp2 = 0;            }        }                for(int x = 0;x < width; ++x){　　　　//上下方向enemy计数            int temp1 = 0;            int temp2 = 0;            for(int y = 0;y < height; ++y){                if(grid[y][x] == 'E') ++temp1;                else if(grid[y][x] == '0') cache[y][x] += temp1;                else temp1 = 0;                                if(grid[height - y - 1][x] == 'E') ++temp2;                else if(grid[height - y - 1][x] == '0') cache[height - y - 1][x] += temp2;                else temp2 = 0;            }        }        int res = 0;        for(int y = 0; y < height; ++y){            for(int x = 0; x < width; ++x){
        　　　　　　　　　 if(grid[y][x] == '0')                　　res = max(res,cache[y][x]);            }        }                return res;    }};