Easy-understanding concise C++ O(mn) solution


  • 11
    X

    Borrow the idea from Product of Array Except Self.

    Create a 2D array count, where count[i][j] indicates how many enemies can be bombed if placing a bomb here. For each row/column, use head to keep track of how many enemies can be bombed from the beginning to current position, use tail to record how many enemies can be bombed from the end to current position. Then update count[i][j].

    For head, If grid[i][j] == ‘W’, set it to 0; else if grid[i][j] == ‘E’, add 1 to it. Same for tail.

    We can combine the updating of head and tail into one loop so that each row/column will only be traversed once.


    class Solution {
    public:
        int maxKilledEnemies(vector<vector<char>>& grid) {
            int i, j, row = grid.size(), col, result, head, tail;
            if(row == 0 || (col = grid[0].size()) == 0)
                return 0;
            vector<vector<int> > count(row, vector<int>(col, 0));
            for(i = 0; i < row; i++) {
                for(head = tail = j = 0; j < col; j++) {
                    count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);
                    count[i][col - 1 - j] = grid[i][col - 1 - j] != '0' ? 0 : (count[i][col - 1 - j] + tail);
                    head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));
                    tail = grid[i][col - 1 - j] == 'W' ? 0 : (tail + (grid[i][col - 1 - j] == 'E' ? 1 : 0));
                }
            }
            for(j = 0; j < col; j++) {
                for(head = tail = i = 0; i < row; i++) {
                    count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);
                    count[row - 1 - i][j] = grid[row - 1 - i][j] != '0' ? 0 : (count[row - 1 - i][j] + tail);
                    head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));
                    tail = grid[row - 1 - i][j] == 'W' ? 0 : (tail + (grid[row - 1 - i][j] == 'E' ? 1 : 0));
                }
            }
            for(i = result = 0; i < row; i++) {
                for(j = 0; j < col; j++) {
                    result = max(result, count[i][j]);
                }
            }
            return result;
        }
    };
    

  • 0

    great idea!!!!


  • 0
    L

    Brilliant solution man! Could you please also share how did you reach to this solution? I mean the starting point where you though that you could do it in this way.


  • 0
    L

    How can I say, such a clever idea. How could u possibly come out that traverse the row and col from both ends and twice.


Log in to reply
 

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