LintCode练习——炸弹袭击（动态规划）

  1 public class Solution {
  2     /**
  3      * @param grid: Given a 2D grid, each cell is either ‘W‘, ‘E‘ or ‘0‘
  4      * @return: an integer, the maximum enemies you can kill using one bomb
  5      */
  6     public int maxKilledEnemies(char[][] grid) {
  7         // write your code here
  8         if (grid == null || grid.length == 0 || grid[0].length == 0) {
  9             return 0;
 10         }
 11 
 12         int m = grid.length;
 13         int n = grid[0].length;
 14 
 15         // 坐标型动态规划
 16         int[][] dp = new int[m][n];
 17         int[][] A = new int[m][n];
 18         
 19         // 依次考虑上下左右四个方向
 20         // up
 21         for (int i = 0; i < m; i++) {
 22             for (int j = 0; j < n; j++) {
 23                 // 初始化为0
 24                 dp[i][j] = 0;
 25                 if (grid[i][j] == ‘W‘) {
 26                     // 如果是墙 ,一票否决
 27                     continue;
 28                 }
 29 
 30                 if (grid[i][j] == ‘E‘) {
 31                     dp[i][j] = 1;
 32                 }
 33 
 34                 if (i - 1 >= 0) {
 35                     dp[i][j] += dp[i - 1][j];
 36                 }
 37 
 38                 // 先做累加
 39                 A[i][j] += dp[i][j];
 40             }
 41         }
 42 
 43         // down
 44         for (int i = m - 1; i >= 0; i--) {
 45             for (int j = 0; j < n; j++) {
 46                 // 初始化为0
 47                 dp[i][j] = 0;
 48                 if (grid[i][j] == ‘W‘) {
 49                     // 如果是墙 ,一票否决
 50                     continue;
 51                 }
 52 
 53                 if (grid[i][j] == ‘E‘) {
 54                     dp[i][j] = 1;
 55                 }
 56 
 57                 if (i + 1 < m) {
 58                     dp[i][j] += dp[i + 1][j];
 59                 }
 60 
 61                 // 先做累加
 62                 A[i][j] += dp[i][j];
 63             }
 64         }
 65 
 66         // left
 67         for (int i = 0; i < m; i++) {
 68             for (int j = 0; j < n; j++) {
 69                 // 初始化为0，防止后面每次都要重置为0
 70                 dp[i][j] = 0;
 71                 if (grid[i][j] == ‘W‘) {
 72                     // 如果是墙 ,一票否决
 73                     continue;
 74                 }
 75 
 76                 if (grid[i][j] == ‘E‘) {
 77                     dp[i][j] = 1;
 78                 }
 79 
 80                 if (j - 1 >= 0) {
 81                     dp[i][j] += dp[i][j - 1];
 82                 }
 83 
 84                 // 先做累加
 85                 A[i][j] += dp[i][j];
 86             }
 87         }
 88 
 89         // right
 90         for (int i = 0; i < m; i++) {
 91             for (int j = n - 1; j >= 0; j--) {
 92                 // 初始化为0
 93                 dp[i][j] = 0;
 94                 if (grid[i][j] == ‘W‘) {
 95                     // 如果是墙 ,一票否决
 96                     continue;
 97                 }
 98 
 99                 if (grid[i][j] == ‘E‘) {
100                     dp[i][j] = 1;
101                 }
102 
103                 if (j + 1 < n) {
104                     dp[i][j] += dp[i][j + 1];
105                 }
106 
107                 // 先做累加
108                 A[i][j] += dp[i][j];
109             }
110         }
111 
112         int ans = 0;
113         // 计算
114         for (int i = 0; i < m; i++) {
115             for (int j = 0; j < n; j++) {
116                 if (grid[i][j] == ‘0‘) {
117                     if (A[i][j] > ans) {
118                         ans = A[i][j];
119                     }
120                 }
121             }
122         }
123 
124         // 返回结果
125         return ans;
126     }
127 }