LeetCode-Bomb Enemy

LeetCode-Bomb Enemy

Posted by Jae on June 30, 2019

1、题目

有一个M*N的网格,每一个格子可能为空,可能有一个敌人,可能有一堵墙,空格子使用'0'表示,敌人用'E'表示,墙使用'W'表示. 只能在某个空格子里放一个炸弹,炸弹会炸死网格所在同行同列的敌人,但是不能穿透墙, 最多能炸死多人敌人?

2、思路

这是一道坐标型动态规划的题,我们可以按照下面四步来分析:

2.1、确定状态

首先分析一个方向(向上)

假设在网格的每一个格子都可以放置炸弹:

如果放到有敌人的格子里,格子里的敌人会被炸死并继续往四个方向炸,

如果放到有墙的格子里,炸弹不会炸死任何敌人

在(i, j)放炸弹

    当(i, j)为空地,炸死的敌人数为(i-1, j)格向上炸死的敌人数;
    当(i, j)有敌人,炸死的敌人数为(i-1, j)格向上炸死的敌人数+1;
    当(i, j)为墙, 炸死的敌人数为0;

原问题:

(i, j)格子放炸弹向上能炸死的敌人数

子问题:

(i-1, j)格子放炸弹向上能炸死的敌人数

状态:

Up[i][j]表示(i, j)格放炸弹向上能炸死的敌人数

2.2、转移方程

             Up[i-1][j]    格子里没有敌人
Up[i][j] =   Up[i-1][j]+1  格子里有敌人
             0             格子里是墙

2.3、 初始条件和边界情况

第0行的Up值与格子相关:

如果格子里是敌人 Up[0][j]=1
如果格子里不是敌人 Up[0][j]=0

2.4、 计算顺序

向上炸的计算顺序从:f[0][0], f[0][1],,, f[m-1][n-1]

分别计算四个方向上能炸死的敌人数,结果 Up[i][j]+Down[i][j]+Left[i][j]+Right[i][j] (i, j)是空地

时间复杂度为O(MN)

空间复杂度为O(MN)

3、实现

public int bombEnemy(char[][] A){
    if (A == null || A.length == 0 || A[0].length == 0){
        return 0;
    }
    int m = A.length;
    int n = A[0].length;

    // Up Down Left Right
    int[][] f = new int[m][n];
    int[][] res = new int[m][n];

    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            // 代表有多少敌人被炸死
            res[i][j] = 0;
        }
    }

    // UP
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j] == 'W'){
                f[i][j] = 0;
            }else{
                f[i][j] = 0;
                // 如果是敌人
                if (A[i][j] == 'E'){
                    f[i][j] = 1;
                }
                // 空地
                if (i > 0){
                    f[i][j] += f[i-1][j];
                }
            }
            res[i][j] += f[i][j];
        }
    }

    // DOWN
    for(int i = m-1; i>=0; i--){
        for(int j= 0; j < n; j++){
            if (A[i][j] == 'W'){
                f[i][j] = 0;
            }else{
                f[i][j] = 0;
                if (A[i][j] == 'E'){
                    f[i][j] = 1;
                }
                if (i + 1 < m){
                    f[i][j] += f[i+1][j];
                }
            }
            res[i][j] += f[i][j];
        }
    }

    // LEFT
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j] == 'W'){
                f[i][j] = 0;
            }else{
                f[i][j] = 0;
                // 如果是敌人
                if (A[i][j] == 'E'){
                    f[i][j] = 1;
                }
                // 空地
                if (j > 0){
                    f[i][j] += f[i][j-1];
                }
            }
            res[i][j] += f[i][j];
        }
    }

    // RIGHT
    for (int i = 0; i < m; i++) {
        for (int j = n-1; j >= 0; j--) {
            if (A[i][j] == 'W'){
                f[i][j] = 0;
            }else{
                f[i][j] = 0;
                // 如果是敌人
                if (A[i][j] == 'E'){
                    f[i][j] = 1;
                }
                // 空地
                if (j + 1 < n){
                    f[i][j] += f[i][j+1];
                }
            }
            res[i][j] += f[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if (A[i][j] == '0'){
                ans = Math.max(ans, res[i][j]);
            }
        }
    }

    return ans;
}