[LeetCode] Bomb Enemy

361. Bomb Enemy

Given an m x n matrix grid where each cell is either a wall ‘W’, an enemy ‘E’ or empty ‘0’, return the maximum enemies you can kill using one bomb. You can only place the bomb in an empty cell.

The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since it is too strong to be destroyed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size(), r = 0, res = 0;
vector<int> c(m,0);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 'W') continue;
if(j == 0 || grid[i][j-1] == 'W') {
r = 0;
int x = j;
while(x < m and grid[i][x] != 'W') {
if(grid[i][x] == 'E') r++;
x++;
}
}
if(i == 0 || grid[i-1][j] == 'W') {
c[j] = 0;
int y = i;
while(y < n and grid[y][j] != 'W') {
if(grid[y][j] == 'E') c[j]++;
y++;
}
}
if(grid[i][j] == '0') {
res = max(res, r + c[j]);
}
}
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
unordered_map<int, map<int, pair<int,int>>> x, y;
int n = grid.size(), m = grid[0].size(), res = 0;
for(int i = 0; i < n; i++) {
int left = 0, right = 0, count = 0;
while(right < m) {
while(left < m and grid[i][left] == 'W') left++;
right = left;
if(left == m) break;

if(grid[i][right] == 'E') count++;
while(right + 1 < m and grid[i][right + 1] != 'W') {
if(grid[i][right+1] == 'E') count++;
right++;
}
if(count)
y[i][left] = {right, count};
count = 0;
right = left = right + 1;
}
}

for(int i = 0; i < m; i++) {
int up = 0, down = 0, count = 0;
while(down < n) {
while(up < n and grid[up][i] == 'W') up++;
down = up;
if(up == n) break;
if(grid[down][i] == 'E') count++;
while(down + 1 < n and grid[down + 1][i] != 'W') {
if(grid[down + 1][i] == 'E') count++;
down++;
}
if(count)
x[i][up] = {down, count};
count = 0;
up = down = down + 1;
}
}


for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] != '0') continue;
auto yBound = y[i].upper_bound(j); //x range
auto xBound = x[j].upper_bound(i); //y range
int count = 0;

if(yBound != y[i].begin()) {
--yBound;
if(yBound->first <= j and j <= yBound->second.first) {
count += yBound->second.second;
}
}

if(xBound != x[j].begin()) {
--xBound;
if(xBound->first <= i and i <= xBound->second.first) {
count += xBound->second.second;
}
}

res = max(res, count);
}
}





return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/17/PS/LeetCode/bomb-enemy/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.