Simple 4-way scan C++ O(mn) solution, self-explaining


  • 0
    Y
    class Solution {
    public:
        int maxKilledEnemies(vector<vector<char>>& grid) {
            int m = grid.size();
            if (m == 0) return 0;
            int n = grid[0].size();
            if (n == 0) return 0;
            
            vector<vector<int>> cnt(m, vector<int> (n, 0));
            int i, j, k, maxKill = 0;
            
            for (j = 0; j < n; j++) {   // scan each column
                k = 0;
                for (i = 0; i < m; i++) {   // top->down
                    if (grid[i][j] == 'E') k++;
                    else if (grid[i][j] == 'W') k = 0;
                    else cnt[i][j] += k;
                }
                
                k = 0;
                for (i = m - 1; i >= 0; i--) {  // down->top
                    if (grid[i][j] == 'E') k++;
                    else if (grid[i][j] == 'W') k = 0;
                    else cnt[i][j] += k;
                }
            }
            
            for (i = 0; i < m; i++) {   // scan each row
                k = 0;
                for (j = 0; j < n; j++) {   // left->right
                    if (grid[i][j] == 'E') k++;
                    else if (grid[i][j] == 'W') k = 0;
                    else cnt[i][j] += k;
                }
                
                k = 0;
                for (j = n - 1; j >= 0; j--) {  // right->left
                    if (grid[i][j] == 'E') k++;
                    else if (grid[i][j] == 'W') k = 0;
                    else { cnt[i][j] += k; maxKill = max(maxKill, cnt[i][j]); }
                }
            }
            
            return maxKill;
        }
    };
    

Log in to reply
 

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