leetcode 361

问题

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: You can only put the bomb at an empty cell.

Example:

1
2
3
4
5
6
7
8
9
Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3 
Explanation: For the given grid,

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

Placing a bomb at (1,1) kills 3 enemies.

分析

思路1: 声明两个辅助矩阵，$hor[i][j]$ 表示在 $(i, j)$ 放炸弹之后该行能够消灭的敌人的数量，$ver[i][j]$ 表示在 $(i, j)$ 放炸弹之后该列能够消灭的敌人的数量。然后再遍历每个点。时间复杂度 $O(mn)$ ，空间复杂度 $O(mn)$。思路2: 声明一个变量 $row$ 代表该行在当前位置能够消灭的该行的敌人的数量。数组 $cols[j]$ 表示在第 $j$ 列的当前位置能够消灭的敌人的数量，这些保存的结果当遇到 W 时进行更新。这样也能保证时间复杂度$O(mn)$，空间复杂度$O(mn)$。

代码1

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
class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        if (m==0 || n==0)
            return 0;
        vector<vector<int>> hor(m, vector<int>(n, 0));
        vector<vector<int>> ver(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'W') {
                    hor[i][j] = ver[i][j] = 0;
                } else {
                    if (grid[i][j] == 'E') {
                        hor[i][j] = ver[i][j] = 1;
                    }
                    if (j>0) hor[i][j] += hor[i][j-1];
                    if (i>0) ver[i][j] += ver[i-1][j];
                }
            }
        }
        for (int i = m-1; i >= 0; --i) {
            for (int j = n-1; j >= 0; --j) {
                if (grid[i][j] != 'w') {
                    if (j<n-1 && grid[i][j+1] != 'W')
                        hor[i][j] = hor[i][j+1];
                    if (i<m-1 && grid[i+1][j] != 'W')
                        ver[i][j] = ver[i+1][j];
                }
            }
        }
        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, hor[i][j] + ver[i][j]);
                }
            }
        }
        return ans;
    }
};

代码2

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
class Solution {
public:
    int getRowEnemies(vector<vector<char>>& grid, int i, int j) {
        int ret = 0;
        int n = grid[0].size();
        while (j < n && grid[i][j] != 'W') {
            ret += grid[i][j]=='E'? 1: 0;
            ++j;
        }
        return ret;
    }
    int getColEnemies(vector<vector<char>>& grid, int i, int j) {
        int ret = 0;
        int m = grid.size();
        while (i < m && grid[i][j] != 'W') {
            ret += grid[i][j]=='E'? 1: 0;
            ++i;
        }
        return ret;
    }
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        if (m==0 || n==0)
            return 0;
        
        int row = 0;
        vector<int> cols(n, 0);
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'W') continue;
                if (j == 0 || grid[i][j-1] == 'W') {
                    row = getRowEnemies(grid, i, j);
                }
                if (i == 0 || grid[i-1][j] == 'W') {
                    cols[j] = getColEnemies(grid, i, j);
                }
                if (grid[i][j] == '0')
                    ans = max(ans, row + cols[j]);
            }
        }
        
        return ans;
    }
};