Clean C++ O(MN) time & space solution with detailed comments


  • 0

    Whether you want to call this "DP solution", I think it is really based on personal philosophy how you want to interpret DP technique.

        int maxKilledEnemies(vector<vector<char>>& g) {
          int m, n, res = 0;
          if (!(m = g.size())||!(n = g[0].size())) return res;
          
          // enemies killed vertically/horizontally at (i,j)
          vector<vector<int>> v(m, vector<int>(n)), h(m, vector<int>(n)); 
          
          // calculate top and left including current location
          // this is also the vertical kills total if location at bottom
          // this is also the horizontal kills total if location at rightmost
          for (int i = 0; i < m; ++i) 
          for (int j = 0; j < n; ++j)
            if (g[i][j] != 'W') {
              h[i][j] = (i? h[i-1][j] : 0) + (g[i][j] == 'E');
              v[i][j] = (j? v[i][j-1] : 0) + (g[i][j] == 'E');
            }
    
          // calculate h[][] and v[][] and max total
          for (int i = m-1; i >= 0; --i) 
          for (int j = n-1; j >= 0; --j)
            if (g[i][j] != 'W') {
              // total horizontal kills must be same if neither (i,j) or (i+1,j) is wall
              if (i+1 < m && h[i+1][j]) h[i][j] = h[i+1][j];
              // total vertical kills must be same if neither (i,j) or (i,j+1) is wall
              if (j+1 < n && v[i][j+1]) v[i][j] = v[i][j+1];
              if (g[i][j] == '0') res = max(res, h[i][j] + v[i][j]);
            }
            
          return res;
        }
    

Log in to reply
 

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