给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 '0'), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固，所以墙不会被摧毁.
样例
样例1
输入:
grid =[
"0E00",
"E0WE",
"0E00"
]
输出: 3
解释:
把炸弹放在 (1,1) 能杀3个敌人
样例2
输入:
grid =[
"0E00",
"EEWE",
"0E00"
]
输出: 2
解释:
P把炸弹放在 (0,0) 或 (0,3) 或 (2,0) 或 (2,3) 能杀2个敌人
注意事项
你只能在空的地方放置炸弹.
/**
* up[i][j] = up[i-1][j] '0'
* -----------up[i-1][j]+1 'E'
* -----------0 'W'
*
* @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) {
// write your code here
int m = grid.length;
if (m == 0) {
return 0;
}
int n = grid[0].length;
if (n == 0) {
return 0;
}
int[][] up = new int[m][n];
int[][] left = new int[m][n];
int[][] right = new int[m][n];
int[][] down = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'W') {
up[i][j] = 0;
continue;
}
up[i][j] = grid[i][j] == 'E' ? 1 : 0;
if (i > 0) {
up[i][j] += up[i - 1][j];
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'W') {
left[i][j] = 0;
continue;
}
left[i][j] = grid[i][j] == 'E' ? 1 : 0;
if (j > 0) {
left[i][j] += left[i][j - 1];
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'W') {
down[i][j] = 0;
continue;
}
down[i][j] = grid[i][j] == 'E' ? 1 : 0;
if (i < m - 1) {
down[i][j] += down[i + 1][j];
}
}
}
for (int i = 0; i < m; i++) {
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 'W') {
right[i][j] = 0;
continue;
}
right[i][j] = grid[i][j] == 'E' ? 1 : 0;
if (j < n - 1) {
right[i][j] += right[i][j + 1];
}
}
}
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0') {
int temp = up[i][j] + left[i][j] + down[i][j] + right[i][j];
res = Math.max(res, temp);
}
}
}
return res;
}
/**
* up[i][j] = up[i-1][j] '0'
* -----------up[i-1][j]+1 'E'
* -----------0 'W'
*
* @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 maxKilledEnemies1(char[][] grid) {
// write your code here
int m = grid.length;
if (m == 0) {
return 0;
}
int n = grid[0].length;
if (n == 0) {
return 0;
}
int[][] up = new int[m][n];
int[][] left = new int[m][n];
int[][] right = new int[m][n];
int[][] down = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'W') {
up[i][j] = 0;
continue;
}
if (grid[i][j] == '0') {
up[i][j] = 0;
if (i > 0) {
up[i][j] += up[i - 1][j];
}
}
if (grid[i][j] == 'E') {
up[i][j] = 1;
if (i > 0) {
up[i][j] += up[i - 1][j];
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'W') {
left[i][j] = 0;
continue;
}
if (grid[i][j] == '0') {
left[i][j] = 0;
if (j > 0) {
left[i][j] += left[i][j - 1];
}
}
if (grid[i][j] == 'E') {
left[i][j] = 1;
if (j > 0) {
left[i][j] += left[i][j - 1];
}
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'W') {
down[i][j] = 0;
continue;
}
if (grid[i][j] == '0') {
down[i][j] = 0;
if (i < m - 1) {
down[i][j] += down[i + 1][j];
}
}
if (grid[i][j] == 'E') {
down[i][j] = 1;
if (i < m - 1) {
down[i][j] += down[i + 1][j];
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 'W') {
right[i][j] = 0;
continue;
}
if (grid[i][j] == '0') {
right[i][j] = 0;
if (j < n - 1) {
right[i][j] += right[i][j + 1];
}
}
if (grid[i][j] == 'E') {
right[i][j] = 1;
if (j < n - 1) {
right[i][j] += right[i][j + 1];
}
}
}
}
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0') {
int temp = up[i][j] + left[i][j] + down[i][j] + right[i][j];
res = Math.max(res, temp);
}
}
}
return res;
}
网友评论