讨论/题目交流/200. 岛屿数量 这个程序为什么会无限循环的执行下去啊?/
200. 岛屿数量 这个程序为什么会无限循环的执行下去啊?

leetcode推荐答案如下:

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int number = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    number++;
                    grid[i][j] = '0';
                    Queue<Integer> queue = new LinkedList<>();
                    queue.offer(i * n + j);
                    while (!queue.isEmpty()) {
                        int c = queue.poll();
                        int x = c / n;
                        int y = c % n;
                        // 顺时针
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            queue.offer((x - 1) * n + y);
                            grid[x - 1][y] = '0';
                        }
                        if (y + 1 < n && grid[x][y + 1] == '1') {
                            queue.offer(x * n + y + 1);
                            grid[x][y + 1] = '0';
                        }
                        if (x + 1 < m && grid[x + 1][y] == '1') {
                            queue.offer((x + 1) * n + y);
                            grid[x + 1][y] = '0';
                        }
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            queue.offer(x * n + y - 1);
                            grid[x][y - 1] = '0';
                        }
                    }
                }
            }
        }
        return number;
    }

本人的解法是:

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int number = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    number++;
                    Queue<Integer> queue = new LinkedList<>();
                    queue.offer(i * n + j);
                    while (!queue.isEmpty()) {
                        int c = queue.poll();
                        int x = c / n;
                        int y = c % n;
                        grid[x][y] = '0';
                        // 顺时针
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            queue.offer((x - 1) * n + y);
                        }
                        if (y + 1 < n && grid[x][y + 1] == '1') {
                            queue.offer(x * n + y + 1);
                        }
                        if (x + 1 < m && grid[x + 1][y] == '1') {
                            queue.offer((x + 1) * n + y);
                        }
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            queue.offer(x * n + y - 1);
                        }
                    }
                }
            }
        }
        return number;
    }

个人感觉我的这个程序逻辑没有问题,而且比leetcode推荐答案好点,但问题是为什么执行的时候回无线循环下去啊 🤣🤣🤣?感谢各位算法大牛指出问题所在。

无限循环的case:

char[][] grid = {
            {'1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '0', '1', '1'},
            {'0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '0'},
            {'1', '0', '1', '1', '1', '0', '0', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '0', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1'},
            {'0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '0', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '0', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'0', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1'},
            {'1', '0', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1', '1', '0', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '0'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '0', '0'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
            {'1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'}
        };
展开讨论
小明同学发起于 2020-03-17

盲猜一个: BFS走回头路了.

展开全部 4 讨论