首页 > 代码库 > Bomb Enemy -- LeetCode
Bomb Enemy -- LeetCode
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:
For the given grid0 E 0 0E 0 W E0 E 0 0return 3. (Placing a bomb at (1,1) kills 3 enemies)思路：扫描矩阵，用rowCount表示该点所在行内有多少敌人可见。用colCount[i]表示该点所在列i内有多少敌人可见。然后该点可见的敌人为两者之和。
初始时两值为0.
当我们位于行首或者该行上一格为墙，那么在该行向右扫描直到行尾或者遇见一堵墙，更新rowCount。
当我们位于列首或者该列上一格为墙，那么在该列向下扫描直到列尾或者遇见一堵墙，更新colCount[i]。
时间复杂度O(mn)，空间复杂度O(N)。
1 class Solution { 2 public: 3 int maxKilledEnemies(vector<vector<char>>& grid) { 4 if (grid.size() == 0) return 0; 5 int rowCount = 0, height = grid.size(), width = grid[0].size(), res = 0; 6 vector<int> colCount(width, 0); 7 for (int i = 0; i < height; i++) { 8 for (int j = 0; j < width; j++) { 9 if (!j || grid[i][j-1] == ‘W‘) {10 rowCount = 0;11 for (int k = j; k < width && grid[i][k] != ‘W‘; k++)12 rowCount += grid[i][k] == ‘E‘;13 }14 if (!i || grid[i-1][j] == ‘W‘) {15 colCount[j] = 0;16 for (int k = i; k < height && grid[k][j] != ‘W‘; k++)17 colCount[j] += grid[k][j] == ‘E‘;18 }19 if (grid[i][j] == ‘0‘)20 res = std::max(res, rowCount + colCount[j]);21 }22 }23 return res;24 }25 };
Bomb Enemy -- LeetCode
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。