Google - 3

Question

Bomb Game，给一个m*n的二维数组，其中有： -1 墙， 1 怪兽， 0 空白。 你有一个炸弹，可以扔在除墙之外的任意位置，最多可以炸死几个怪兽。
炸弹爆炸可以清除这个炸弹所在的一行和一列的怪兽，但是不能穿过墙.

Algorithm

Create a matrix with same number of row and column like input matrix. This matrix stores values that for each point, how many monsters at left and top including itself. Create a array whose size is number of columns of input matrix. This array stores how many monsters at top of current point. For each row, we create a max variable to store how many monsters at left of the point.

Code

public int getMax(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int[][] num = new int[rows][cols]
    int[] topMax = new int[cols];
    for (int i = 0; i < rows; i++) {
        int leftMax = 0;
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == -1) {
                leftMax = 0;
                topMax[j] = 0;
                num[i][j] = 0;
            } else {
                if (j == 0) {
                    leftMax = matrix[i][j];
                } else {
                    leftMax += matrix[i][j];
                }
                if (i == 0) {
                    topMax[j] = matrix[i][j];
                } else {
                    topMax[j] += matrix[i][j];
                }
                num[i][j] = topMax[j] + leftMax;
            }
        }
    }
    int[] bottomMax = new int[cols];
    int totalMax = 0;
    for (int i = rows - 1; i >= 0; i--) {
        int rightMax = 0;
        for (int j = cols - 1; j >= 0; j--) {
            if (matrix[i][j] == -1) {
                rightMax = 0;
                bottomMax[j] = 0;
            } else {
                if (j == cols - 1) {
                    rightMax = matrix[i][j];
                } else {
                    rightMax += matrix[i][j];
                }
                if (i == rows - 1) {
                    bottomMax[j] = matrix[i][j];
                } else {
                    bottomMax[j] += matrix[i][j];
                }
                int tempMax = num[i][j] + bottomMax[j] + rightMax;
                if (matrix[i][j] == 1) {
                    tempMax -= 3;
                }
                totalMax = Math.max(tempMax, totalMax);
           }
       }
    }
    return totalMax;
}