lc361

發表於   |   分類於   |   0 comments   |  

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:

1
2
3
4
5
6
7
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)

这道题是……泡泡堂？

可能是受grid illumination的影响，最开始的想法是，遍历一遍保存下来每行每列的enemy count，碰到墙就把这个vector切割（pushback新元素0）；在每个0的位置放炸弹的效果就是把对应的行/列enemy count数加起来就好。但因为要找到被墙分割以后在count数组中的位置，时间复杂度较高。

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 {
    vector<vector<int>> row_walls, col_walls;
    vector<vector<int>> row_cnt, col_cnt;
    int m, n;
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        m = grid.size();
        if (!m) return 0;
        n = grid[0].size();
        vector<vector<int>> cnt(m, vector<int>(n,0));
        for (int i = 0; i < m; i++) {
            row_cnt.push_back(vector<int>{0});
            row_walls.push_back(vector<int>{});
        }
        for (int j = 0; j < n; j++) {
            col_cnt.push_back(vector<int>{0});
            col_walls.push_back(vector<int>{});
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'E') {
                    row_cnt[i][row_cnt[i].size()-1]++;
                    col_cnt[j][col_cnt[j].size()-1]++;
                }
                if (grid[i][j] == 'W') {
                    row_cnt[i].push_back(0);
                    row_walls[i].push_back(j);
                    col_cnt[j].push_back(0);
                    col_walls[j].push_back(i);
                }
            }
        }
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') continue;
                int w = 0;
                while (w < row_walls[i].size() && row_walls[i][w] < j) {
                    w++;
                }
                cnt[i][j] += row_cnt[i][w];
                
                w = 0;
                while (w < col_walls[j].size() && col_walls[j][w] < i) {
                    w++;
                }
                cnt[i][j] += col_cnt[j][w];
                // cout << i << " " << j << " " << cnt[i][j] << endl;
                if (cnt[i][j] > max) max = cnt[i][j];
            }
        }
        return max;
        
    }
};

用DP来做的话，从前往后遍历一遍，从后往前遍历一遍，分别用之前算的结果算当前的值，时间复杂度O(mn)。

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
class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        if (!m) return 0;
        int n = grid[0].size();
        vector<vector<int>> rcnt1(m, vector<int>(n,0)), rcnt2(m, vector<int>(n,0));
        vector<vector<int>> ccnt1(m, vector<int>(n,0)), ccnt2(m, vector<int>(n,0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'W')  {rcnt1[i][j] = 0; ccnt1[i][j] = 0;}
                else {
                    rcnt1[i][j] += (grid[i][j]=='E');
                    ccnt1[i][j] += (grid[i][j]=='E');
                    if (i > 0) rcnt1[i][j] += rcnt1[i-1][j];
                    if (j > 0) ccnt1[i][j] += ccnt1[i][j-1];
                }
            }
        }
        
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (grid[i][j] == 'W')  {rcnt2[i][j] = 0; ccnt2[i][j] = 0;}
                else {
                    rcnt2[i][j] += (grid[i][j]=='E');
                    ccnt2[i][j] += (grid[i][j]=='E');
                    if (i < m-1) rcnt2[i][j] += rcnt2[i+1][j];
                    if (j < n-1) ccnt2[i][j] += ccnt2[i][j+1];
                }
            }
        }
        
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') continue;
                int cnt = rcnt1[i][j] + rcnt2[i][j] + ccnt1[i][j] + ccnt2[i][j];
                if (cnt > max) max = cnt;
            }
        }
        return max;
        
    }
};

减少空间的常数项，可以只用一个cnt矩阵，前后的enemy信息用常数表示。

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();
        if (!m) return 0;
        int n = grid[0].size();
        vector<vector<int>> cnt1(m, vector<int>(n,0));
        for (int i = 0; i < m; i++) {
            int f = 0, b = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'W')  f = 0; 
                if (grid[i][n-j-1] == 'W') b = 0;
                f += grid[i][j]=='E';
                b += grid[i][n-j-1]=='E';
                if (grid[i][j] == '0') cnt1[i][j] += f;
                if (grid[i][n-j-1] == '0') cnt1[i][n-j-1] += b;
            }
        }
        
        for (int j = 0; j < n; j++) {
            int f = 0, b = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 'W')  f = 0; 
                if (grid[m-i-1][j] == 'W') b = 0;
                f += grid[i][j]=='E';
                b += grid[m-i-1][j]=='E';
                if (grid[i][j] == '0') cnt1[i][j] += f;
                if (grid[m-i-1][j] == '0') cnt1[m-i-1][j] += b;
            }
        }
        
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') continue;
                if (cnt1[i][j] > max) max = cnt1[i][j];
            }
        }
        return max;
        
    }
};