CS Mines Flood Fill问题Java解决方案超时优化求助

核心优化思路：砍掉集合类的额外开销 #

Java的HashSet/TreeSet在频繁插入、查询时的哈希计算、树结构维护会带来可观性能损耗，尤其在Flood Fill这类需要大量坐标操作的场景下。以下是具体落地方案：

• 用二维布尔数组替代集合标记访问状态
  直接创建与输入网格同尺寸的boolean[][] visited数组，标记已处理的坐标。数组的直接内存访问是O(1)操作，完全规避哈希冲突、集合扩容等额外开销。代码片段示例：

  boolean[][] visited = new boolean[rows][cols];
  // 处理坐标(x,y)时
  if (!visited[x][y] && grid[x][y] == targetColor) {
      visited[x][y] = true;
      // 加入队列/栈执行BFS/DFS
  }
  

• 优先选择BFS遍历，避免递归DFS的栈开销
  Java递归DFS会产生栈帧开销，深度过大还可能触发栈溢出。改用基于ArrayDeque的BFS，它的出队入队操作比LinkedList更高效（底层为数组实现）：

  Deque<Integer> xQueue = new ArrayDeque<>();
  Deque<Integer> yQueue = new ArrayDeque<>();
  xQueue.add(startX);
  yQueue.add(startY);
  visited[startX][startY] = true;
  
  while (!xQueue.isEmpty()) {
      int x = xQueue.poll();
      int y = yQueue.poll();
      // 遍历上下左右四个方向
      for (int[] dir : dirs) {
          int nx = x + dir[0];
          int ny = y + dir[1];
          if (nx >= 0 && nx < rows && ny >= 0 && ny < cols 
              && !visited[nx][ny] && grid[nx][ny] == targetColor) {
              visited[nx][ny] = true;
              xQueue.add(nx);
              yQueue.add(ny);
          }
      }
  }
  

• 减少循环内的对象创建
  避免在遍历中频繁创建int[]坐标对象，拆分x、y到两个单独队列存储，能降低GC压力：

  // 替代int[]数组队列，用两个单独队列存x、y
  Deque<Integer> xQueue = new ArrayDeque<>();
  Deque<Integer> yQueue = new ArrayDeque<>();
  

• 重写IO逻辑，提速输入输出
  Java默认Scanner和System.out.println速度较慢，改用BufferedReader读取输入，StringBuilder拼接输出后一次性打印，大幅减少IO耗时：

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  int rows = Integer.parseInt(br.readLine());
  int cols = Integer.parseInt(br.readLine());
  char[][] grid = new char[rows][cols];
  for (int i = 0; i < rows; i++) {
      grid[i] = br.readLine().trim().toCharArray();
  }
  
  // 处理完成后输出
  StringBuilder sb = new StringBuilder();
  for (char[] row : grid) {
      sb.append(row).append('\n');
  }
  System.out.print(sb);
  

额外细节优化 #

• 把方向数组设为静态常量，避免每次遍历重复创建：

  private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  

• 若题目要求输出填充的坐标集合，用ArrayList存储所有坐标后再一次性排序，比TreeSet实时排序效率高得多。

内容的提问来源于stack exchange，提问作者Mandeep Singh