Java straightforward solution DP O(mn) time and space


  • 38

    The code might be a little bit long and there should exist more elegant one.
    However the idea of this very straightforward. We do simply two traversals. One from upper left to bottom right, for each spot we compute enemies to its left and up including itself. The other traversal is from bottom right to upper left, we compute enemies to its right and down and in the same time we add them up all to find the maxKill. Any suggestion to make it more concise?

    public class Solution {
        public int maxKilledEnemies(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            int m = grid.length, n = grid[0].length;
            Spot[][] spots = new Spot[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    spots[i][j] = new Spot();
                    if (grid[i][j] == 'W') {
                        continue;
                    }
                    spots[i][j].up = (i == 0 ? 0 : spots[i - 1][j].up) + (grid[i][j] == 'E' ? 1 : 0);
                    spots[i][j].left = (j == 0 ? 0 : spots[i][j - 1].left) + (grid[i][j] == 'E' ? 1 : 0);
                }
            }
            
            int maxKill = 0;
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    if (grid[i][j] == 'W') {
                        continue;
                    }
                    spots[i][j].bottom = (i == m - 1 ? 0 : spots[i + 1][j].bottom) + (grid[i][j] == 'E' ? 1 : 0);
                    spots[i][j].right = (j == n - 1 ? 0 : spots[i][j + 1].right) + (grid[i][j] == 'E' ? 1 : 0);
                    
                    if (grid[i][j] == '0') {
                        maxKill = Math.max(maxKill, spots[i][j].up + spots[i][j].left + spots[i][j].bottom + spots[i][j].right);
                    }
                }
            }
            return maxKill;
        }
    }
    
    class Spot {
        int up; // enemies to its up including itself
        int left; // enemies to its left including itself
        int bottom;
        int right;
    }

  • 1
    Q

    Thanks, this is the real dp solution. Like the new object to solve the problem. Good idea.


  • 1
    C

    This is very intuitive ! Thank you !


  • 0
    Z

    very very clear solution!


  • 3
    A

    Thanks for sharing !
    The basic idea of my C++ solution is practically close to yours. I think mine is a bit more concise cause I only record the enemies on the left and on the top for each cell. Hope it can be of some use.

    int maxKilledEnemies(vector<vector<char>>& grid) {
            if (grid.size() == 0) return 0;
            int m = grid.size(), n = grid[0].size(), max_kill = 0;
            vector<vector<int>> left(m, vector<int>(n, 0));//Numbers of enemies on the left, including current cell
            vector<vector<int>> up(m, vector<int>(n, 0));//Numbers of enemies on the above, including current cell
            
            for(int i = 0; i < m; ++ i) {
                for(int j = 0; j < n; ++ j) {
                    if (grid[i][j] == 'E') {
                        if (i > 0 && grid[i - 1][j] != 'W') up[i][j] = up[i - 1][j] + 1;
                        else up[i][j] = 1;
                        if (j > 0 && grid[i][j - 1] != 'W') left[i][j] = left[i][j - 1] + 1;
                        else left[i][j] = 1;
                    }
                    else {
                        if (i > 0 && grid[i - 1][j] != 'W') up[i][j] = up[i - 1][j];
                        if (j > 0 && grid[i][j - 1] != 'W') left[i][j] = left[i][j - 1];
                    }
                }
            }
            for(int i = m - 1; i >= 0; -- i) {
                for(int j = n - 1; j >= 0; -- j) {//Assign the correct value backwards, unless a wall is encountered
                    if (i > 0 && grid[i - 1][j] != 'W') up[i - 1][j] = up[i][j];
                    if (j > 0 && grid[i][j - 1] != 'W') left[i][j - 1] = left[i][j];
                    if (grid[i][j] == '0') max_kill = max(max_kill, up[i][j] + left[i][j]);
                }
            }
            return max_kill;
    }
    
    

  • 0
    K

    @shuxu

    class Solution {
        public int maxKilledEnemies(char[][] grid) {
            int n = grid.length;
            if (n == 0) return 0;
            int m = grid[0].length;
            if (m == 0) return 0;
            
            int rowEnemiesCount = 0;
            int[] colEnemiesCounts = new int[m];
            
            for (int r = 0; r < n; r ++) {
                for (int c = 0; c < m; c ++) {
                    switch(grid[r][c]) {
                        case 'E':
                            rowEnemiesCount ++;
                            colEnemiesCounts[c] ++ ;
                            break;
                        case 'W':
                            rowEnemiesCount = 0;
                            colEnemiesCounts[c] = 0;
                            break;
                        default:
                            grid[r][c] = (char)(rowEnemiesCount + colEnemiesCounts[c]);
                    }
                }
                rowEnemiesCount = 0;
            }
            
            Arrays.fill(colEnemiesCounts, 0);
            int max = 0;
            for (int r = n - 1; r >= 0; r --) {
                for (int c = m - 1; c >= 0; c --) {
                    switch(grid[r][c]) {
                        case 'E':
                            rowEnemiesCount ++;
                            colEnemiesCounts[c] ++ ;
                            break;
                        case 'W':
                            rowEnemiesCount = 0;
                            colEnemiesCounts[c] = 0;
                            break;
                        default:
                            grid[r][c] += rowEnemiesCount + colEnemiesCounts[c];
                            max = Math.max(max, grid[r][c]);
                    }
                }
                rowEnemiesCount = 0;
            }
            
            return max;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.