## Saturday, June 18, 2016

### LeetCode 361 - Bomb Enemy

https://discuss.leetcode.com/topic/10/bomb-enemy/
Given a 2D grid, each cell is either a wall `'W'`, an enemy `'E'` or empty `'0'` (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.
Example:
```For the given grid

0 E 0 0
E 0 W E
0 E 0 0

return 3. (Placing a bomb at (1,1) kills 3 enemies)```
Main goal is how to use less space
X. https://discuss.leetcode.com/topic/48565/short-o-mn-time-o-n-space-solution
Walk through the matrix. At the start of each non-wall-streak (row-wise or column-wise), count the number of hits in that streak and remember it. O(mn) time, O(n) space.
``````int maxKilledEnemies(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
int result = 0, rowhits, colhits[n];
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (!j || grid[i][j-1] == 'W') {
rowhits = 0;
for (int k=j; k<n && grid[i][k] != 'W'; k++)
rowhits += grid[i][k] == 'E';
}
if (!i || grid[i-1][j] == 'W') {
colhits[j] = 0;
for (int k=i; k<m && grid[k][j] != 'W'; k++)
colhits[j] += grid[k][j] == 'E';
}
if (grid[i][j] == '0')//
result = max(result, rowhits + colhits[j]);
}
}
return result;
}``````
https://discuss.leetcode.com/topic/48742/simple-dp-solution-in-java
only need to store one killed enemies value for a row and an array of each column;
if current grid value is W, this means previous stored value becomes invalid, you need to recalculate.
I think it is O(m * n). Although there is another for loop k inside for loops of i and j. It just calculates the enemies in advance. In the end, it will traverse this grid once to compute the enemies that are killed.

it is little a DP-like SOLUTION, the only place col[], which is storing col enemies count, is only updated once for consecutive enemies column, and reused for later calculation (when there is '0', where bomb can be planted)

`````` public int maxKilledEnemies(char[][] grid) {
if(grid == null || grid.length == 0 ||  grid[0].length == 0) return 0;
int max = 0;
int row = 0;
int[] col = new int[grid[0].length];
for(int i = 0; i<grid.length; i++){
for(int j = 0; j<grid[0].length;j++){
if(grid[i][j] == 'W') continue;
if(j == 0 || grid[i][j-1] == 'W'){
row = killedEnemiesRow(grid, i, j);
}
if(i == 0 || grid[i-1][j] == 'W'){
col[j] = killedEnemiesCol(grid,i,j);
}
if(grid[i][j] == '0'){//
max = (row + col[j] > max) ? row + col[j] : max;
}
}

}

return max;
}

//calculate killed enemies for row i from column j
private int killedEnemiesRow(char[][] grid, int i, int j){
int num = 0;
while(j <= grid[0].length-1 && grid[i][j] != 'W'){
if(grid[i][j] == 'E') num++;
j++;
}
return num;
}
//calculate killed enemies for  column j from row i
private int killedEnemiesCol(char[][] grid, int i, int j){
int num = 0;
while(i <= grid.length -1 && grid[i][j] != 'W'){
if(grid[i][j] == 'E') num++;
i++;
}
return num;
}``````
X. O(mn) space
https://discuss.leetcode.com/topic/48603/java-straightforward-solution-dp-o-mn-time-and-space
The code might be a little bit long and there should exist more elegant one.
However the idea of this very straightforward. We do simply two traversals. One from upper left to bottom right, for each spot we compute enemies to its left and up including itself. The other traversal is from bottom right to upper left, we compute enemies to its right and down and in the same time we add them up all to find the maxKill.
``````    public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
Spot[][] spots = new Spot[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
spots[i][j] = new Spot();
if (grid[i][j] == 'W') {
continue;
}
spots[i][j].up = (i == 0 ? 0 : spots[i - 1][j].up) + (grid[i][j] == 'E' ? 1 : 0);
spots[i][j].left = (j == 0 ? 0 : spots[i][j - 1].left) + (grid[i][j] == 'E' ? 1 : 0);
}
}

int maxKill = 0;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (grid[i][j] == 'W') {
continue;
}
spots[i][j].bottom = (i == m - 1 ? 0 : spots[i + 1][j].bottom) + (grid[i][j] == 'E' ? 1 : 0);
spots[i][j].right = (j == n - 1 ? 0 : spots[i][j + 1].right) + (grid[i][j] == 'E' ? 1 : 0);

if (grid[i][j] == '0') {
maxKill = Math.max(maxKill, spots[i][j].up + spots[i][j].left + spots[i][j].bottom + spots[i][j].right);
}
}
}
return maxKill;
}
class Spot {
int up; // enemies to its up including itself
int left; // enemies to its left including itself
int bottom;
int right;
}``````
X.
https://discuss.leetcode.com/topic/49109/straightforward-o-mn-java-solution-49ms
``````public int maxKilledEnemies(char[][] grid) {
int rowNum = grid.length;
if (rowNum == 0) return 0;
int colNum = grid[0].length;

int[][] fromBottom = new int[rowNum][colNum];
int[][] fromRight = new int[rowNum][colNum];

for (int i = rowNum - 1; i >= 0; i--) {
for (int j = colNum - 1; j >= 0; j--) {
int enemy = grid[i][j] == 'E' ? 1 : 0;
if (grid[i][j] != 'W') {
fromBottom[i][j] = (i == rowNum - 1) ? enemy : fromBottom[i+1][j] + enemy;
fromRight[i][j] = (j == colNum - 1) ? enemy : fromRight[i][j+1] + enemy;
}
else {
fromBottom[i][j] = 0;
fromRight[i][j] = 0;
}
}
}

int[] fromTop = new int[colNum];
int[] fromLeft = new int[rowNum];
int max = 0;

for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
if (grid[i][j] != '0') {
fromTop[j] = grid[i][j] == 'W' ? 0 : fromTop[j] + 1;
fromLeft[i] = grid[i][j] == 'W' ? 0 : fromLeft[i] + 1;
}
else {
int num = fromTop[j] + fromLeft[i] + fromBottom[i][j] + fromRight[i][j];
max = Math.max(num, max);
}
}
}
return max;
}``````
http://www.cnblogs.com/grandyang/p/5599289.html

```    int maxKilledEnemies(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<int>> v1(m, vector<int>(n, 0)), v2 = v1, v3 = v1, v4 = v1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int t = (j == 0 || grid[i][j] == 'W') ? 0 : v1[i][j - 1];
v1[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
for (int j = n - 1; j >= 0; --j) {
int t = (j == n - 1 || grid[i][j] == 'W') ? 0 : v2[i][j + 1];
v2[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
}
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m; ++i) {
int t = (i == 0 || grid[i][j] == 'W') ? 0 : v3[i - 1][j];
v3[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
for (int i = m - 1; i >= 0; --i) {
int t = (i == m - 1 || grid[i][j] == 'W') ? 0 : v4[i + 1][j];
v4[i][j] = grid[i][j] == 'E' ? t + 1 : t;
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') {
res = max(res, v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]);
}
}
}
return res;
}```

https://discuss.leetcode.com/topic/52170/share-my-java-codes
X. https://leetcode.com/discuss/109116/short-o-mn-solution

https://discuss.leetcode.com/topic/48565/short-o-mn-solution
``````int maxKilledEnemies(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
int result = 0, rowhits, colhits[n];
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (!j || grid[i][j-1] == 'W') {
rowhits = 0;
for (int k=j; k<n && grid[i][k] != 'W'; k++)
rowhits += grid[i][k] == 'E';
}
if (!i || grid[i-1][j] == 'W') {
colhits[j] = 0;
for (int k=i; k<m && grid[k][j] != 'W'; k++)
colhits[j] += grid[k][j] == 'E';
}
if (grid[i][j] == '0')
result = max(result, rowhits + colhits[j]);
}
}
return result;
}``````
https://discuss.leetcode.com/topic/48577/short-java-accepted-solution-55ms
``````public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int ret = 0;
int row = grid.length;
int col = grid[0].length;
int rowCache = 0;
int[] colCache = new int[col];
for (int i = 0;i < row; i++) {
for (int j = 0; j < col; j++) {
if (j == 0 || grid[i][j-1] == 'W') {
rowCache = 0;
for (int k = j; k < col && grid[i][k] != 'W'; k++) {
rowCache += grid[i][k] == 'E' ? 1 : 0;
}
}
if (i == 0 || grid[i-1][j] == 'W') {
colCache[j] = 0;
for (int k = i;k < row && grid[k][j] != 'W'; k++) {
colCache[j] += grid[k][j] == 'E' ? 1 :0;
}
}
if (grid[i][j] == '0') {
ret = Math.max(ret, rowCache + colCache[j]);
}
}
}
return ret;
}``````

http://dartmooryao.blogspot.com/2016/06/leetcode-361-bomb-enemy.html
My idea is to create a 2D matrix, and go from Left, Right, Top, and Down to calculate the count. Then add the count into the 2D matrix.

This solution is better because the code looks much shorter.

Idea:
(1) Use a 1D array to store the current count of the previous cols, and another int variable to store the count from the left.
(2) Use two for loops to visit all elements in the matrix.
(3) When the left of current position is a wall, we reset the rowHit variable to 0. Then we use a for loop that start from current position to the right, adding the count of E to the rowHit. Until we hit a wall.
(4) When the top col is a wall, we reset the colHit to be zero. Then use the same way to calculate the colHit to the end of col.
(5) If the current position is a '0', we compare the rowHit+colHit with the max result.
public int maxKilledEnemies(char[][] grid) {
if(grid.length==0){ return 0; }
int rowNo = grid.length, colNo = grid[0].length;
int[] colHit = new int[colNo];
int rowHit = 0;
int result = 0;

for(int i=0; i<rowNo; i++){
for(int j=0; j<colNo; j++){
if(j==0 || grid[i][j-1]=='W'){
rowHit = 0;
for(int k=j; k<colNo && grid[i][k] != 'W'; k++){
if(grid[i][k]=='E'){ rowHit++; }
}
}

if(i==0 || grid[i-1][j]=='W'){
colHit[j] = 0;
for(int k=i; k<rowNo && grid[k][j] != 'W'; k++){
if(grid[k][j]=='E'){ colHit[j]++; }
}
}

if(grid[i][j]=='0'){
result = Math.max(result, rowHit+colHit[j]);
}
}
}

return result;
}

Walk through the matrix. At the start of each non-wall-streak (row-wise or column-wise), count the number of hits in that streak and remember it. O(mn) time, O(n) space.
``````int maxKilledEnemies(vector<vector<char>>& grid) {
int m = grid.size(), n = m ? grid[0].size() : 0;
int result = 0, rowhits, colhits[n];
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (!j || grid[i][j-1] == 'W') {
rowhits = 0;
for (int k=j; k<n && grid[i][k] != 'W'; k++)
rowhits += grid[i][k] == 'E';
}
if (!i || grid[i-1][j] == 'W') {
colhits[j] = 0;
for (int k=i; k<m && grid[k][j] != 'W'; k++)
colhits[j] += grid[k][j] == 'E';
}
if (grid[i][j] == '0')
result = max(result, rowhits + colhits[j]);
}
}
return result;
}``````
https://leetcode.com/discuss/109134/short-java-accepted-solution-55ms
public int maxKilledEnemies(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int ret = 0; int row = grid.length; int col = grid[0].length; int rowCache = 0; int[] colCache = new int[col]; for (int i = 0;i < row; i++) { for (int j = 0; j < col; j++) { if (j == 0 || grid[i][j-1] == 'W') { rowCache = 0; for (int k = j; k < col && grid[i][k] != 'W'; k++) { rowCache += grid[i][k] == 'E' ? 1 : 0; } } if (i == 0 || grid[i-1][j] == 'W') { colCache[j] = 0; for (int k = i;k < row && grid[k][j] != 'W'; k++) { colCache[j] += grid[k][j] == 'E' ? 1 :0; } } if (grid[i][j] == '0') { ret = Math.max(ret, rowCache + colCache[j]); } } } return ret; }
X. Brute Force
https://discuss.leetcode.com/topic/51035/super-straightforward-java-solution/
Isn't this a Brute force way with Time complexity O(m^2 + n^2) ?
https://leetcode.com/discuss/109110/simple-java-solution-easy-to-understand
public int maxKilledEnemies(char[][] grid) { if (grid == null || grid.length == 0) return 0; int ret=0; for (int i=0; i<grid.length; i++) { for (int j=0; j<grid[0].length; j++) { if (grid[i][j] != '0') continue; ret = Math.max(ret, countKilled(i, j, grid)); } } return ret; } int countKilled(int row, int col, char[][] grid) { int ret=0; for (int i=row; i<grid.length && grid[i][col] != 'Y'; i++) { if (grid[i][col] == 'X') ret++; } for (int i=row; i>=0 && grid[i][col] != 'Y'; i--) { if (grid[i][col] == 'X') ret++; } for (int i=col; i<grid[0].length && grid[row][i] != 'Y'; i++) { if (grid[row][i] == 'X') ret++; } for (int i=col; i>=0 && grid[row][i] != 'Y'; i--) { if (grid[row][i] == 'X') ret++; } return ret; }

https://discuss.leetcode.com/topic/50374/java-dp-solultion-o-mn-time-o-mn-space-beats-90
Using only `O(mn)` memory for additional grid (not as perfect as (`O(m)` space solutions given by other users but anyway..) we can solve this problem through `O(4mn)` iterations. We just need to scan the grid from left to right and accumulate the sum of enemies by `dp[i][j]` from left since the last wall. Then we do the same from top to bottom, from right to left and finally from bottom to top. On each iteration we increase the `dp[i][j]` value by cumulative sum.
``````  public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];

// from left to right
for (int i = 0; i < m; i++) {
int current = 0;
for (int j = 0; j < n; j++)
current = process(grid, dp, i, current, j);
}
// from top to bottom
for (int j = 0; j < n; j++) {
int current = 0;
for (int i = 0; i < m; i++)
current = process(grid, dp, i, current, j);
}
// from right to left
for (int i = 0; i < m; i++) {
int current = 0;
for (int j = n - 1; j >= 0; j--)
current = process(grid, dp, i, current, j);
}
int ans = 0;
// from bottom to top
for (int j = 0; j < n; j++) {
int current = 0;
for (int i = m - 1; i >= 0; i--) {
current = process(grid, dp, i, current, j);
if (grid[i][j] == '0')  ans = Math.max(ans, dp[i][j]);
}
}

return ans;
}

private int process(char[][] c, int[][] dp, int i, int current, int j) {
if (c[i][j] == 'W') current = 0;
if (c[i][j] == 'E') current++;
dp[i][j] += current;
return current;
}``````

https://all4win78.wordpress.com/2016/07/24/leetcode-361-bomb-enemy/

`    ``public` `int` `maxKilledEnemies(``char``[][] grid) {`
`        ``if` `(grid == ``null` `|| grid.length == ``0``) {`
`            ``return` `0``;`
`        ``}`
`        `
`        ``int``[][] enemyCount = ``new` `int``[grid.length][``2``];`
`        ``for` `(``int` `i = ``0``; i < enemyCount.length; i++) {`
`            ``enemyCount[i][``0``] = -``1``;`
`        ``}`
`        `
`        ``int` `max = ``0``;`
`        ``for` `(``int` `j = ``0``; j < grid[``0``].length; j++) {`
`            ``int` `colEnemy = countColEnemy(grid, j, ``0``);`
`            ``for` `(``int` `i = ``0``; i < grid.length; i++) {`
`                ``if` `(grid[i][j] == ``'0'``) {`
`                    ``if` `(j > enemyCount[i][``0``]) {`
`                        ``update(enemyCount, grid, i, j);`
`                    ``}`
`                    ``max = Math.max(colEnemy + enemyCount[i][``1``], max);`
`                ``}`
`                ``if` `(grid[i][j] == ``'W'``) {`
`                    ``colEnemy = countColEnemy(grid, j, i + ``1``);`
`                ``}`
`            ``}`
`        ``}`
`        ``return` `max;`
`    ``}`
`    `
`    ``private` `void` `update(``int``[][] enemyCount, ``char``[][] grid, ``int` `i, ``int` `j) {`
`        ``int` `count = ``0``;`
`        ``int` `k = enemyCount[i][``0``] + ``1``;`
`        ``while` `(k < grid[``0``].length && (grid[i][k] != ``'W'` `|| k < j)) {`
`            ``if` `(grid[i][k] == ``'E'``) {`
`                ``count += ``1``;`
`            ``}`
`            ``if` `(grid[i][k] == ``'W'``) {`
`                ``count = ``0``;`
`            ``}`
`            ``k += ``1``;`
`        ``}`
`        ``enemyCount[i][``0``] = k;`
`        ``enemyCount[i][``1``] = count;`
`    ``}`
`    `
`    ``private` `int` `countColEnemy(``char``[][] grid, ``int` `j, ``int` `start) {`
`        ``int` `count = ``0``;`
`        ``int` `i = start;`
`        ``while` `(i < grid.length && grid[i][j] != ``'W'``) {`
`            ``if` `(grid[i][j] == ``'E'``) {`
`                ``count += ``1``;`
`            ``}`
`            ``i += ``1``;`
`        ``}`
`        ``return` `count;`
`    ``}`

X.
https://fishercoder.com/2016/07/12/bomb-enemy/
https://discuss.leetcode.com/topic/53511/straightforward-java-solution-with-space-complex-o-1
https://discuss.leetcode.com/topic/51035/super-straightforward-java-solution
``````public int maxKilledEnemies(char[][] grid) {
int m = grid.length;
if(grid == null || m == 0) return 0;
int n = grid[0].length;

int[][] max = new int[m][n];

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){

if(grid[i][j] == '0'){
int count = 0;

//count all possible hits in its upward direction
for(int k = j-1; k >= 0; k--){
if(grid[i][k] == 'E') {
count++;
} else if(grid[i][k] == 'W') {
break;
}
}

//count all possible hits in its downward direction
for(int k = j+1; k < n; k++){
if(grid[i][k] == 'E') {
count++;
} else if(grid[i][k] == 'W') {
break;
}
}

//count all possible hits in its right direction
for(int k = i+1; k < m; k++){
if(grid[k][j] == 'E') {
count++;
} else if(grid[k][j] == 'W') {
break;
}
}

//count all possible hits in its left direction
for(int k = i-1; k >= 0; k--){
if(grid[k][j] == 'E') {
count++;
} else if(grid[k][j] == 'W') {
break;
}
}

max[i][j] = count;

}
}
}

int result = 0;

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(max[i][j] > result) result = max[i][j];
}
}
return result;
}``````