题目描述
给你一个大小为 m x n 的矩阵 grid ，其中每个单元格都放置有一个字符：
'W' 表示一堵墙'E' 表示一个敌人'0'（数字 0）表示一个空位
返回你使用 一颗炸弹 可以击杀的最大敌人数目。你只能把炸弹放在一个空位里。
由于炸弹的威力不足以穿透墙体，炸弹只能击杀同一行和同一列没被墙体挡住的敌人。
示例 1：
输入：grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
输出：3
示例 2：
输入：grid = [["W","W","W"],["0","0","0"],["E","E","E"]]
输出：1
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid[i][j] 可以是 'W'、'E' 或 '0'
解法
方法一
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 | class Solution:
def maxKilledEnemies(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
g = [[0] * n for _ in range(m)]
for i in range(m):
t = 0
for j in range(n):
if grid[i][j] == 'W':
t = 0
elif grid[i][j] == 'E':
t += 1
g[i][j] += t
t = 0
for j in range(n - 1, -1, -1):
if grid[i][j] == 'W':
t = 0
elif grid[i][j] == 'E':
t += 1
g[i][j] += t
for j in range(n):
t = 0
for i in range(m):
if grid[i][j] == 'W':
t = 0
elif grid[i][j] == 'E':
t += 1
g[i][j] += t
t = 0
for i in range(m - 1, -1, -1):
if grid[i][j] == 'W':
t = 0
elif grid[i][j] == 'E':
t += 1
g[i][j] += t
return max(
[g[i][j] for i in range(m) for j in range(n) if grid[i][j] == '0'],
default=0,
)
|
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 | class Solution {
public int maxKilledEnemies(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] g = new int[m][n];
for (int i = 0; i < m; ++i) {
int t = 0;
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'W') {
t = 0;
} else if (grid[i][j] == 'E') {
++t;
}
g[i][j] += t;
}
t = 0;
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] == 'W') {
t = 0;
} else if (grid[i][j] == 'E') {
++t;
}
g[i][j] += t;
}
}
for (int j = 0; j < n; ++j) {
int t = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 'W') {
t = 0;
} else if (grid[i][j] == 'E') {
++t;
}
g[i][j] += t;
}
t = 0;
for (int i = m - 1; i >= 0; --i) {
if (grid[i][j] == 'W') {
t = 0;
} else if (grid[i][j] == 'E') {
++t;
}
g[i][j] += t;
}
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') {
ans = Math.max(ans, g[i][j]);
}
}
}
return ans;
}
}
|
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 | class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> g(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
int t = 0;
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'W')
t = 0;
else if (grid[i][j] == 'E')
++t;
g[i][j] += t;
}
t = 0;
for (int j = n - 1; j >= 0; --j) {
if (grid[i][j] == 'W')
t = 0;
else if (grid[i][j] == 'E')
++t;
g[i][j] += t;
}
}
for (int j = 0; j < n; ++j) {
int t = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 'W')
t = 0;
else if (grid[i][j] == 'E')
++t;
g[i][j] += t;
}
t = 0;
for (int i = m - 1; i >= 0; --i) {
if (grid[i][j] == 'W')
t = 0;
else if (grid[i][j] == 'E')
++t;
g[i][j] += t;
}
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') ans = max(ans, g[i][j]);
}
}
return ans;
}
};
|
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 | func maxKilledEnemies(grid [][]byte) int {
m, n := len(grid), len(grid[0])
g := make([][]int, m)
for i := range g {
g[i] = make([]int, n)
}
for i := 0; i < m; i++ {
t := 0
for j := 0; j < n; j++ {
if grid[i][j] == 'W' {
t = 0
} else if grid[i][j] == 'E' {
t++
}
g[i][j] += t
}
t = 0
for j := n - 1; j >= 0; j-- {
if grid[i][j] == 'W' {
t = 0
} else if grid[i][j] == 'E' {
t++
}
g[i][j] += t
}
}
for j := 0; j < n; j++ {
t := 0
for i := 0; i < m; i++ {
if grid[i][j] == 'W' {
t = 0
} else if grid[i][j] == 'E' {
t++
}
g[i][j] += t
}
t = 0
for i := m - 1; i >= 0; i-- {
if grid[i][j] == 'W' {
t = 0
} else if grid[i][j] == 'E' {
t++
}
g[i][j] += t
}
}
ans := 0
for i, row := range grid {
for j, v := range row {
if v == '0' && ans < g[i][j] {
ans = g[i][j]
}
}
}
return ans
}
|