qualtrics 面筋

又想了想之前写的不大对，BFS的step是一个地雷半径内所有的点，修改之后的代码。

1. public class Bomb {
   
2. 
   
3.     int[][] DIRS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   
4. 
   
5.     public int solution(int[][] grid, int row, int col) {
   
6.         Queue<int[]> q = new LinkedList<>();
   
7.         q.add(new int[]{row, col});
   
8.         boolean[][] visited = new boolean[grid.length][grid[0].length];
   
9.         visited[row][col] = true;
   
10.         int res = 1;
    
11.         while (!q.isEmpty()) {
    
12.             int size = q.size();
    
13.             for (int i = 0; i < size; i++) {
    
14.                 int[] pos = q.remove();
    
15.                 int r = pos[0];
    
16.                 int c = pos[1];
    
17.                 int range = grid[r][c];
    
18.                 for (int j = r - range; j <= r + range; j++) {
    
19.                     for (int k = c - range; k <= c + range; k++) {
    
20.                         if (j < 0 || j >= grid.length || k < 0 || k >= grid[0].length || (j - r) * (j - r) + (k - c) * (k - c) > range * range || grid[j][k] == 0 || visited[j][k]) continue;
    
21.                         res++;
    
22.                         visited[j][k] = true;
    
23.                         q.add(new int[]{j, k});
    
24.                     }
    
25.                 }
    
26.             }
    
27.         }
    
28. 
    
29.         return res;
    
30.     }
    
31. 
    
32.     public static void main(String[] args) {
    
33.         Bomb solution = new Bomb();
    
34.         int[][] grid = new int[][]{{1, 2, 0, 0},{0, 0, 1, 0}, {0, 2, 0, 0}, {1, 0, 0, 1}};
    
35.         System.out.println(solution.solution(grid, 0, 0));
    
36.     }
    
37. }
    

复制代码