361. Bomb Enemy

2019-12-11

LeetCode

我们先假设有敌人和有墙的位置都可以放炸弹，这样可以简化问题。

炸弹在上下左右四个方向的效果都是一样的，所以我们可以只考虑炸弹伤害向上传播的情况。我们设up[i][j]为：在(i, j)放炸弹向上炸死的敌人数目。

如果格子里有敌人，炸死的敌人数目是up[i][j] + 1
如果格子里是墙，炸死的敌人数目是0
如果格子是空地，炸死的敌人数目是up[i][j]

又因为在格子(i, j)放炸弹能炸死的敌人数目和它上面一个格子炸死的一样，我们可以得到状态转移方程：

up[i][j] = up[i - 1][j]，如果(i, j)是空地
up[i][j] = up[i - 1][j] + 1 ，如果(i, j)有敌人
up[i][j] = 0 ，如果(i, j)有墙

然后考虑边界条件：

up[0][j] = 1，如果(0, j)有敌人
up[0][j] = 0，如果(0, j)没敌人

接下来我们就可以从上到下计算up[i][j]了。类似地，我们可以计算down[i][j]、left[i][j]和right[i][j]（注意计算顺序有变化，确保子问题先被计算）。

得到四个方向能炸死的敌人数以后，我们设f[i][j]为在(i, j)放炸弹能够炸死的敌人数，有：

f[i][j] = max{up[i][j] + down[i][j] + left[i][j] + right[i][j] }（其中a[i][j] = '0'）

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        int m = grid.length;
        if (m == 0) {
            return 0;
        }
        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++) {
                if (i == 0) {
                    up[i][j] = grid[i][j] == 'E' ? 1 : 0;
                } else {
                    if (grid[i][j] == 'W') {
                        up[i][j] = 0;
                    } else if (grid[i][j] == 'E') {
                        up[i][j] = up[i - 1][j] + 1;
                    } else {
                        up[i][j] = up[i - 1][j];
                    }
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (i == m - 1) {
                    down[i][j] = grid[i][j] == 'E' ? 1 : 0;
                } else {
                    if (grid[i][j] == 'W') {
                        down[i][j] = 0;
                    } else if (grid[i][j] == 'E') {
                        down[i][j] = down[i + 1][j] + 1;
                    } else {
                        down[i][j] = down[i + 1][j];
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    left[i][j] = grid[i][j] == 'E' ? 1 : 0;
                } else {
                    if (grid[i][j] == 'W') {
                        left[i][j] = 0;
                    } else if (grid[i][j] == 'E') {
                        left[i][j] = left[i][j - 1] + 1;
                    } else {
                        left[i][j] = left[i][j - 1];
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (j == n - 1) {
                    right[i][j] = grid[i][j] == 'E' ? 1 : 0;
                } else {
                    if (grid[i][j] == 'W') {
                        right[i][j] = 0;
                    } else if (grid[i][j] == 'E') {
                        right[i][j] = right[i][j + 1] + 1;
                    } else {
                        right[i][j] = right[i][j + 1];
                    }
                }
            }
        }
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    int sum = up[i][j] + down[i][j] + left[i][j] + right[i][j];
                    result = Math.max(result, sum);
                }
            }
        }
        return result;
    }
}