描述
给定一个二维矩阵, 每一个格子可能是一堵墙 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个敌人
思路:通过4种方向的动态规划,解决问题
递推公式:
1.当前位置是wall,dp[i][j] = 0;
2.当前位置是enemy,dp[i][j]=前一种状态+1;
3.当前位置是0,dp[i][j] = 前一种状态;
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) {
// write your code here
if(grid.length==0) return 0;
int m = grid.length;
int n = grid[0].length;
int[][] up = new int[m][n];
int[][] down = new int[m][n];
int[][] left = new int[m][n];
int[][] right = new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int a = m-i-1;
int b = n-j-1;
if(i==0)
{
if(grid[i][j]=='E') up[i][j] = 1;
else up[i][j] = 0;
}
else{
if(grid[i][j]=='E') up[i][j] = up[i-1][j]+1;
else if(grid[i][j]=='W') up[i][j] =0;
else up[i][j] = up[i-1][j];
}
if(i==0)
{
if(grid[a][j]=='E') down[a][j] = 1;
else down[a][j] = 0;
}
else{
if(grid[a][j]=='E') down[a][j] = down[a+1][j]+1;
else if(grid[a][j]=='W') down[a][j] =0;
else down[a][j] = down[a+1][j];
}
if(j==0)
{
if(grid[i][j]=='E') left[i][j] = 1;
else left[i][j] = 0;
}
else{
if(grid[i][j]=='E') left[i][j] = left[i][j-1]+1;
else if(grid[i][j]=='W') left[i][j] =0;
else left[i][j] = left[i][j-1];
}
if(j==0)
{
if(grid[i][b]=='E') right[i][b] = 1;
else right[i][b] = 0;
}
else{
if(grid[i][b]=='E') right[i][b] = right[i][b+1]+1;
else if(grid[i][b]=='W') right[i][b] =0;
else right[i][b] = right[i][b+1];
}
}
}
int x=-1,y=-1;
int[][] arr = new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
arr[i][j] = up[i][j] +down[i][j] +right[i][j]+left[i][j];
//System.out.println(up[i][j] +" "+down[i][j]+" "+right[i][j]+" "+left[i][j]);
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='0'){
if(x==-1){
x=i;
y=j;
}else if(arr[x][y]<arr[i][j]){
x = i;
y=j;
}
}
}
}
if(x==-1) return 0;
return arr[x][y];
}
}