O(mn) C++ solution


  • 0
    N
    class Solution {
    public:
        inline void update(const char c, int & inc, int & val)
        {
            switch(c)
            {
                case 'E' : inc++; 
                return;
                case 'W' : inc = 0;
                return; 
                default: 
                val += inc;
                return;
            }
        }
        
        int maxKilledEnemies(vector<vector<char>>& grid) {
            int rows = grid.size();
            if(!rows) { return 0; }
            int cols = grid[0].size();
            
            vector<vector<int>> ig(rows,vector<int>(cols,0));
            
            // move row
            for(int i = 0; i < rows; ++i)
            {
                int inc = 0;
                //left to right
                for(int j = 0; j < cols; ++j)
                {
                    update(grid[i][j], inc, ig[i][j]);
                }
                
                //right to left
                inc = 0;
                for(int j = cols-1; j >= 0; --j)
                {
                    update(grid[i][j], inc, ig[i][j]);
                }
            }
            
        
            // move col
            for(int j = 0; j < cols; ++j)
            {
                // up to down
                int inc = 0;
                for(int i = 0; i < rows; ++i)
                {
                    update(grid[i][j], inc, ig[i][j]);
                }
                
                //down to up
                inc = 0;
                for(int i = rows-1; i >= 0; --i)
                {
                    update(grid[i][j], inc, ig[i][j]);
                }
            }
    
            int max_val = 0;
            
            for(int i = 0; i < rows; ++i)
            {
                for(int j = 0; j < cols; ++j)
                {
                    max_val = max(max_val,ig[i][j]);
                }
            }
            return max_val;
        }
    };
    
    

Log in to reply
 

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