C++ well abstracted solution


  • 0
    H

    My solution in 4 steps using a memoization algorithm and one additional mxn grid

    /*
    Enumerating rows and columns:
    0 1, 2, ... n-1
    1
    2
    .
    m-1
    */
    
        void addKilledToCell(int i, int j, int& enemies, vector<vector<int> >& killed, char content) {
            if (content == 'W') {
                enemies = 0;
            } else if (content == 'E') {
            enemies++;
            } else {
                killed[i][j] += enemies;
            }
        }
    
        void addRightKilled(const vector<vector<char> >& grid, vector<vector<int> >& killed) {
            int m = grid.size(), n = grid[0].size();
            int enemies;
            for (int j=0; j<n; j++) {
                enemies = 0;
                for(int i=m-1; i>=0; i--) {
                    addKilledToCell(i, j, enemies, killed, grid[i][j]);
                }
            }
        }
    
        void addLeftKilled(const vector<vector<char> >& grid, vector<vector<int> >& killed) {
            int m = grid.size(), n = grid[0].size();
            int enemies;
                for (int j=0; j<n; j++) {
                    enemies = 0;
                    for(int i=0; i<m; i++) {
                        addKilledToCell(i, j, enemies, killed, grid[i][j]);
                    }
            }
        }
    
        void addTopKilled(const vector<vector<char> >& grid, vector<vector<int> >& killed) {
            int m = grid.size(), n = grid[0].size();
            int enemies;
            for (int i=0; i<m; i++) {
                enemies = 0;
                for(int j=0; j<n; j++) {
                    addKilledToCell(i, j, enemies, killed, grid[i][j]);
                }
            }
        }
    
        void addBottomKilled(const vector<vector<char> >& grid, vector<vector<int> >& killed) {
            int m = grid.size(), n = grid[0].size();
            int enemies;
                for (int i=0; i<m; i++) {
                    enemies = 0;
                    for(int j=n-1; j>=0; j--) {
                        addKilledToCell(i, j, enemies, killed, grid[i][j]);
                    }
            }
        }
    
        int findMaximum(const vector<vector<char> >&grid, const vector<vector<int> >& killed) {
            int m = grid.size(), n = grid[0].size();
            int maximum = 0;
            for(int i=0; i<m; i++) {
                for(int j=0; j<n; j++) {
                    if(grid[i][j]=='0' && killed[i][j] > maximum) {
                        maximum = killed[i][j];
                    }
                }
            }
            return maximum;
        }
    
        int maxKilledEnemies(vector<vector<char> > grid ) {
            int m = grid.size();
            if (m==0) return 0;
            int n = grid[0].size();
            vector<vector<int> > killed(m, vector<int>(n, 0));
            addLeftKilled(grid, killed);
            addRightKilled(grid, killed);
            addTopKilled(grid, killed);
            addBottomKilled(grid, killed);
    
            return findMaximum(grid, killed);
        }
    
    };
    
    

Log in to reply
 

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