lintcode 553 · 炸弹袭击【中等 数组+bfs+模拟】

题目

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个敌人
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路

BFS+模拟： 队列首先存放所有空的坐标。然后针对每一个空的坐标，往上走，往下走，往左走，往右走
统计遇到的E的个数cnt。遇到W就停止。取每一个坐标对应的cnt的最大值就是答案。注意数组为空的情况
1
2

答案

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;

        Queue<int[]> 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 max=Integer.MIN_VALUE;
        while (!q.isEmpty()){
            int[] cur = q.poll();
            int x = cur[0],y=cur[1];
            int x1 = x-1;
            int cnt = 0;
            while (x1>=0) { //向上走
                if(grid[x1][y] =='E')
                    cnt++;
                if(grid[x1][y] =='W')
                    break;
                x1--;
            }
            x1 = x+1;
            while (x1<n) { //向下走
                if(grid[x1][y] =='E')
                    cnt++;
                if(grid[x1][y] =='W')
                    break;
                x1++;
            }

            int y1 = y-1;
            while (y1>=0) { //向左走
                if(grid[x][y1] =='E')
                    cnt++;
                if(grid[x][y1] =='W')
                    break;
                y1--;
            }

            y1 = y+1;
            while (y1 < m) { //向右走
                if(grid[x][y1] =='E')
                    cnt++;
                if(grid[x][y1] =='W')
                    break;
                y1++;
            }

            max = Math.max(cnt,max);
        }
        return max;
    }
}
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
57
58
59
60
61
62
63
64