‘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.
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
思路：
预处理出每个点向四个方向能炸到的人数，然后枚举所有点，取最大值即可
public class Solution {
/**
* @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
*/
public int maxKilledEnemies(char[][] grid) {
int m = grid.length;
int n = m > 0 ? grid[0].length : 0;
int result = 0, rows = 0;
int[] cols = new int[n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (j == 0 || grid[i][j-1] == ‘W‘) {
rows = 0;
for (int k = j; k < n && grid[i][k] != ‘W‘; ++k)
if (grid[i][k] == ‘E‘)
rows += 1;
}
if (i == 0 || grid[i-1][j] == ‘W‘) {
cols[j] = 0;
for (int k = i; k < m && grid[k][j] != ‘W‘; ++k)
if (grid[k][j] == ‘E‘)
cols[j] += 1;
}
if (grid[i][j] == ‘0‘ && rows + cols[j] > result)
result = rows + cols[j];
}
}
return result;
}
}
原文：https://www.cnblogs.com/FLAGyuri/p/12078566.html