easy understand c++ solution


  • 0

    Use two 2-D matrix to record the "can bomb" enemy in each row and col.
    Scan the row when j==0||grid[i][j-1]=='W'
    Scan the col when i==0||grid[i-1][j]=='W'
    Maybe it is a O(mn) solution?

        int maxKilledEnemies(vector<vector<char>>& grid) {
            if(grid.empty())
                return 0;
            int m=grid.size();
            int n=grid[0].size();
            vector<vector<int>> rows(m,vector<int>(n,-1));
            vector<vector<int>> cols(m,vector<int>(n,-1));
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(grid[i][j]=='W'){
                        continue;
                    }
                    if(i==0||grid[i-1][j]=='W'){
                        int count=0;
                        int row=i;
                        while(row<m){
                            if(grid[row][j]=='W')
                                break;
                            else if(grid[row][j]=='E')
                                count++;
                            row++;
                        }
                        cols[i][j]=count;
                    }
                    if(j==0||grid[i][j-1]=='W'){
                        int count=0;
                        int col=j;
                        while(col<n){
                            if(grid[i][col]=='W')
                                break;
                            else if(grid[i][col]=='E')
                                count++;
                            col++;
                        }
                        rows[i][j]=count;
                    }
                    if(rows[i][j]==-1)
                        rows[i][j]=rows[i][j-1];
                    if(cols[i][j]==-1)
                        cols[i][j]=cols[i-1][j];
                }
            }
            int res=0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(grid[i][j]=='0'){
                        res=max(rows[i][j]+cols[i][j],res);
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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