# Easy-understanding concise C++ O(mn) solution

• Borrow the idea from Product of Array Except Self.

Create a 2D array `count`, where `count[i][j]` indicates how many enemies can be bombed if placing a bomb here. For each row/column, use `head` to keep track of how many enemies can be bombed from the beginning to current position, use `tail` to record how many enemies can be bombed from the end to current position. Then update `count[i][j]`.

For `head`, If grid[i][j] == ‘W’, set it to 0; else if grid[i][j] == ‘E’, add 1 to it. Same for `tail`.

We can combine the updating of `head` and `tail` into one loop so that each row/column will only be traversed once.

``````class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
int i, j, row = grid.size(), col, result, head, tail;
if(row == 0 || (col = grid[0].size()) == 0)
return 0;
vector<vector<int> > count(row, vector<int>(col, 0));
for(i = 0; i < row; i++) {
for(head = tail = j = 0; j < col; j++) {
count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);
count[i][col - 1 - j] = grid[i][col - 1 - j] != '0' ? 0 : (count[i][col - 1 - j] + tail);
head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));
tail = grid[i][col - 1 - j] == 'W' ? 0 : (tail + (grid[i][col - 1 - j] == 'E' ? 1 : 0));
}
}
for(j = 0; j < col; j++) {
for(head = tail = i = 0; i < row; i++) {
count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);
count[row - 1 - i][j] = grid[row - 1 - i][j] != '0' ? 0 : (count[row - 1 - i][j] + tail);
head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));
tail = grid[row - 1 - i][j] == 'W' ? 0 : (tail + (grid[row - 1 - i][j] == 'E' ? 1 : 0));
}
}
for(i = result = 0; i < row; i++) {
for(j = 0; j < col; j++) {
result = max(result, count[i][j]);
}
}
return result;
}
};
``````

• great idea!!!!

• Brilliant solution man! Could you please also share how did you reach to this solution? I mean the starting point where you though that you could do it in this way.

• How can I say, such a clever idea. How could u possibly come out that traverse the row and col from both ends and twice.

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