C++ solution, beats 99%


  • 0
    H

    When traversing through the grid, if we reached a position that either has a wall in front of/above it, or is at the beginning of a row/column, keep track off the length of current streak on both directions. For example:
    0 E 0 0 E 0
    0 E 0 0 0 0
    E 0 W E 0 E
    0 E 0 0 E 0

    When I'm at position (0,0), my horizontal length is 2, and vertical length is 1. So the number of enemies that can be reached is 3. And as I move along the first row to the right, I can keep using the same horizontal length without recalculating, untill I hit a wall or the edge of the grid. Same goes to the elements that are in the same column. If I'm at position (2,1), my horizontal length is 1 (because the presence of the wall), and my vertical length is 3. Then I will hit the wall before I get to position (2,4). Once I get through the wall I need to reset my horizontal length. Thus at (2,4) my horizontal length becomes 2, and vertical length is 2. We do the same thing as we are moving down.

    public:
        int maxKilledEnemies(vector<vector<char>>& grid) {
            if (grid.size() == 0) return 0;
            int m = grid.size();
            int n = grid[0].size();
            vector<int> rows (m,0);
            vector<int> cols (n,0);
            int result = 0;
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 || grid[i-1][j] == 'W') {
                        for (int k = i; k < m && grid[k][j]!='W'; k++) 
                            cols[j] += (grid[k][j] == 'E');
                    }
                    
                    if (j == 0 || grid[i][j-1] == 'W') {
                        for (int k = j; k < n && grid[i][k]!='W'; k++)
                            rows[i] += (grid[i][k] == 'E');
                    }
                    
                    if (grid[i][j] == 'W') {
                        rows[i] = 0;
                        cols[j] = 0;
                    }
                    if (grid[i][j] == '0') {
                        result = max(result, rows[i]+cols[j]); 
                    }
                }
            }
            
            return result;
        }
    };

Log in to reply
 

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