C++ O(mn) Memory Search, Easy Understand, somehow stop at 46/47


  • 0
    Y

    Wrong Answer: 46/47 0utput: 703, Expected: 708

    class Solution {
    public:
        int maxKilledEnemies(vector<vector<char>>& grid) {
            if (grid.size() == 0) return 0;
            vector<int> resT(grid[0].size(),0);
            vector<vector<int>> resM(grid.size(), resT);// resultMatrix
            int res = 0;// result
            for (int i = 0; i < grid.size(); i++)
                for (int j = 0; j < grid[0].size(); j++) 
                    if (grid[i][j] == 'E' && resM[i][j] == 0) {
                        int s = i+1, n = i-1, e = j+1, w = j-1; //south, north, east, west
                        int sumR = 1, sumC = 1;//numbers of 'E' in this Row and Column
                        // record numbers of 'E' in this row
                        while (s < grid.size() && grid[s][j] != 'W') {
                            if (grid[s][j] == 'E') sumR++;
                            s++;
                        }
                        while (n >= 0  && grid[n][j] != 'W') {
                            if (grid[n][j] == 'E') sumR++;
                            n--;
                        }
                        for (int q = ++n; q < s; q++) {// write into resultMatrix   
                            resM[q][j] += sumR;
                            if (isdigit(grid[q][j])) res = max(res, resM[q][j]);
                        }
                        // record numbers 'E' in this column
                        while (e < grid[0].size()  && grid[i][e] != 'W') {
                            if (grid[i][e] == 'E') sumC++;
                            e++;
                        }
                        while (w >= 0  && grid[i][w] != 'W') {
                            if (grid[i][w] == 'E') sumC++;
                            w--;
                        }
                        for (int q = ++w; q < e; q++) {// write into resultMatrix   
                            resM[i][q] += sumC;
                            if (isdigit(grid[i][q])) res = max(res, resM[i][q]);
                        }
                    }
            return res;
        }
    };
    

Log in to reply
 

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