轰炸敌人，最多可以摧毁的敌人城堡数目

我的解法：

对于每一个空位置，进行一次bfs，从上下左右四个方向去寻找，这是岛屿问题的相似处理，但是这个题可以优化，因为横竖方向可以进行动规优化。

我们不需要对每个0都重新数一遍它所在的行和列有多少敌人。

• 行：对于同一行里、两个墙之间的所有格子，它们能炸到的“行敌人”数量是一样的。我们只在行的开头或者刚经过一个墙之后，重新计算当前这段的敌人数量。

• 列：同理，对于同一列里、两个墙之间的所有格子，它们能炸到的“列敌人”数量也是一样的。我们可以用一个数组colHits[]来缓存每一列当前段的敌人数量。

#include <vector> #include <algorithm> using namespace std; class Solution { public: int maxKilledEnemies(vector<vector<char>>& grid) { if (grid.empty() || grid[0].empty()) return 0; int m = grid.size(); int n = grid[0].size(); int result = 0; int rowHits = 0; // 缓存当前行这一段（两墙之间）的敌人数量 vector<int> colHits(n, 0); // 缓存每一列当前段的敌人数量 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { // 1. 处理行：如果是行的开头，或者前一个是墙，就需要重新统计这一段行里的敌人 if (j == 0 || grid[i][j-1] == 'W') { rowHits = 0; // 向右扫描直到碰到墙或边界 for (int k = j; k < n && grid[i][k] != 'W'; ++k) { if (grid[i][k] == 'E') rowHits++; } } // 2. 处理列：如果是列的开头，或者上面一个是墙，就需要重新统计这一段列里的敌人 if (i == 0 || grid[i-1][j] == 'W') { colHits[j] = 0; // 向下扫描直到碰到墙或边界 for (int k = i; k < m && grid[k][j] != 'W'; ++k) { if (grid[k][j] == 'E') colHits[j]++; } } // 3. 只有当前位置是空位 '0' 时，才能放炸弹 if (grid[i][j] == '0') { result = max(result, rowHits + colHits[j]); } } } return result; } };

2511. 最多可以摧毁的敌人城堡数目

e摧毁的敌人城堡数目，所以我们返回 4 。

class Solution { public: int captureForts(vector<int>& forts) { int res = 0; int pre = -1; // 表示不存在 for(int i = 0; i < forts.size(); i++) { if(forts[i] != 0) { if(pre >= 0 && forts[i] != forts[pre]) // 1 和 -1 或者 -1 和 1出现 res = max(res, i - pre - 1); pre = i; } } return res; } };