BFS解岛屿被淹没问题

Question

为什么我用bfs写的代码超时了呢，通过率只有40%，官方给的题解也是bfs
希望各位指点一下，谢谢
题目

我写的代码

package beikao18;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//全球变暖
public class GlobalWarm {
    public static  char[][] map;
    public static int ans = 0;
    static int[] dr = {1,-1,0,0};
    static int[] dc = {0,0,1,-1};
    public static Queue<Node> q = new LinkedList<>();
    static boolean[][] visted;
    static boolean willYanMo;


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        map = new char[N][N];
        visted= new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String next = scanner.next();
            for (int j = 0; j < N; j++) {
                map[i][j] = next.charAt(j);
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N ; j++) {

                if(map[i][j] == '#' && visted[i][j] == false){
                    bfs(i,j);
                    if(willYanMo == true){
                        ans++;
                    }
                }

            }
        }

        System.out.println(ans);

    }

    private static  void bfs(int r, int c){
         willYanMo = true;
        //添加源点
        q.add(new Node(r,c));

        while (!q.isEmpty()){
            //拓展原点
            Node n = q.poll();
            visted[n.r][n.c] = true;
            int flag =0; //标记陆地周围的海水数量
            for (int i = 0; i < 4; i++) {

                int newR = n.r + dr[i];
                int newC = n.c + dc[i];
                if(newR >= 0 && newR < map.length && newC >= 0 && newC < map.length &&  map[newR][newC] == '.'){
                   flag++;
                }
                if(newR >= 0 && newR < map.length && newC >= 0 && newC < map.length && map[newR][newC] == '#' && visted[newR][newC] == false){
                    q.add(new Node(newR,newC));

                }
            }
            if(flag == 0){
                willYanMo = false;
            }
        }


    }

    static class Node{
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }


}

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

针对使用BFS写的超时问题，可以考虑以下几点： 1.优化数据结构的选择。使用队列的话，每个点的拓展会进行多次的入队和出队操作。对于复杂度较高的题目，可以尝试使用双端队列等数据结构。 2.优化拓展方式。在拓展每个点时，可以利用已经拓展过的点的信息，避免重复拓展。同时，可以通过剪枝等方式减少拓展的情况，从而减少时间复杂度。 3.优化程序的实现。例如可以使用位运算等高效操作代替除法、取模等操作，从而提高程序效率。 以下是一份优化BFS的代码示例：

import java.util.ArrayDeque;
import java.util.Queue;
public class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            // 首尾节点不可达
            return -1;
        }
        Queue<Integer> queue = new ArrayDeque<>();
        // 将起点加入队列，并标记为已访问
        queue.offer(0);
        grid[0][0] = 1;
        int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
        int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int curr = queue.poll();
                int r = curr / n;
                int c = curr % n;
                if (r == n - 1 && c == n - 1) {
                    // 已到达终点
                    return steps + 1;
                }
                for (int k = 0; k < 8; k++) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                        queue.offer(nr * n + nc);
                        grid[nr][nc] = 1;
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}