设计一个网站策划书,织梦网站安装dir,网站备案号 信息,最近一周的新闻热点事件题目
https://www.lintcode.com/problem/553
给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 0), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固#xff0c;所以墙不会被摧毁.你只…题目
https://www.lintcode.com/problem/553
给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 0), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固所以墙不会被摧毁.你只能在空的地方放置炸弹.样例
样例1输入:
grid [0E00,E0WE,0E00
]
输出: 3
解释:
把炸弹放在 (1,1) 能杀3个敌人
样例2输入:
grid [ 0E00, EEWE, 0E00]
输出: 2
解释:
P把炸弹放在 (0,0) 或 (0,3) 或 (2,0) 或 (2,3) 能杀2个敌人思路
BFS模拟 队列首先存放所有空的坐标。然后针对每一个空的坐标往上走往下走往左走往右走
统计遇到的E的个数cnt。遇到W就停止。取每一个坐标对应的cnt的最大值就是答案。注意数组为空的情况答案
public class Solution {/*** param grid: Given a 2D grid, each cell is either W, E or 0* return: an integer, the maximum enemies you can kill using one bomb*/public int maxKilledEnemies(char[][] grid) {if (grid null || grid.length 0|| grid[0]null|| grid[0].length 0)return 0;int n grid.length,m grid[0].length;Queueint[] q new LinkedList(); //存储所有空的地方for (int i 0; i n ; i) {for (int j 0; j m ; j) {if(grid[i][j] 0){q.add(new int[]{i,j});}}}if(q.size() 0) return 0; //没有空的地方int maxInteger.MIN_VALUE;while (!q.isEmpty()){int[] cur q.poll();int x cur[0],ycur[1];int x1 x-1;int cnt 0;while (x10) { //向上走if(grid[x1][y] E)cnt;if(grid[x1][y] W)break;x1--;}x1 x1;while (x1n) { //向下走if(grid[x1][y] E)cnt;if(grid[x1][y] W)break;x1;}int y1 y-1;while (y10) { //向左走if(grid[x][y1] E)cnt;if(grid[x][y1] W)break;y1--;}y1 y1;while (y1 m) { //向右走if(grid[x][y1] E)cnt;if(grid[x][y1] W)break;y1;}max Math.max(cnt,max);}return max;}
}
