最后更新
二刷
11-Jan-2017
首先，正常做的话，是每个格子都纵向横向CHECK一下，这样复杂度爆炸。。
看起来是用dp[][]记录情况，避免重复计算。但是这样的话，得有2个dp[][]，分别记录某一个格子可在横向和纵向分别干死多少敌人。 空间复杂度又爆炸。。O(2MN)
不过可以优化。
遍历的时候是从上往下，从左往右，所以对于grid[i][j]来说，假如他左边也是炸弹，那他横向能消灭多少敌人 和 左边格子横向消灭敌人数量一致。
纵向看他上面是不是炸弹，是的话也和上面能消灭的纵向敌人的数量一致。
所以对于一个格子，如果他左面或者上面是炸弹，可以直接用上面的数据，否则就要重新计算需要的方向，最后2个方向加起来。
空间上，每一行用一个变量记录能干死多少人就行了，纵向得一维数组，记录上一行这个位置能干死几个。
叙述挺麻烦，看眼代码一目了然。
Time Complexity:
O(MN)? 不会做，每个格子遍历，但是貌似worst case不太肯定，WORSTCASE是2个方向都要测一下，这也就意味着下一行下一列的格子不需要这样做了。。所以= =不确定。
Space: O(N)
public class Solution {
public int maxKilledEnemies(char[][] grid) {
if (grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
int rowKill = 0;
int[] colKill = new int[cols];
int res = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// horizontal
if (j == 0 || grid[i][j-1] == 'W') {
rowKill = 0;
for (int t = j; t < cols && grid[i][t] != 'W'; t++) {
if (grid[i][t] == 'E') rowKill ++;
}
}
// vertical
if (i == 0 || grid[i-1][j] == 'W') {
colKill[j] = 0;
for (int t = i; t < rows && grid[t][j] != 'W'; t++) {
if (grid[t][j] == 'E') colKill[j] ++;
}
}
int tempTotal = rowKill + colKill[j];
if (grid[i][j] == '0') {
res = Math.max(res, tempTotal);
}
}
}
return res;
}
}
一刷
14-Oct-2016
这个题确实不会。。只能想到naive的做法，不过那样应该是O(n³)，不会满足要求。
看TAG是DP，那应该是建立DP[][]记录每点可炸的情况。一个点如果左边/上边是墙，或者左边/上边是边界，就要重新计算，否则跟左边/上边的那个格子的情况一样。 是空位就来一发，然后取最大。
这样应该是mn的extra space，时间变成（常数，但是不知道是什么。。）*n²。
不是很确定，看了答案，发现很巧妙。。
因为遍历是在一行一行的基础上，每列每列，所以没必要MN的extra space，一个变量记录每行的情况，过了那一行就自动更新，另一个int[cols]记录每列的情况就行了。。
时间上还是常熟*（n²)
public class Solution
{
public int maxKilledEnemies(char[][] grid)
{
if(grid.length == 0) return 0;
int res = 0;
int row = 0;
int[] col = new int[grid[0].length];
for(int i = 0; i < grid.length;i++)
{
for(int j = 0; j < grid[0].length;j++)
{
if(i == 0 || grid[i-1][j] == 'W')
{
col[j] = 0;
int t = i;
while(t < grid.length && grid[t][j] != 'W')
{
if(grid[t][j] == 'E') col[j]++;
t++;
}
}
if(j == 0 || grid[i][j-1] == 'W')
{
row = 0;
int t = j;
while(t < grid[0].length && grid[i][t] != 'W')
{
if(grid[i][t] == 'E') row++;
t++;
}
}
if(grid[i][j] == '0') res = Math.max(res,col[j]+row);
}
}
return res;
}
}