200. Number of Islands - Medium

前往題目

這題看到grid，看到題目內文，應該就是BFS了吧，第一眼看起來也很像union-find。

雖然知道了，但Code寫不出來，於是去看了官神的影片，這題他debug了一陣子才找到小小的錯誤，variable寫錯，整體邏輯是完全沒問題的。

看完後自己實作一遍，沒想到除了一些語句上的問題之外，邏輯一次就過了，比起上次看到BFS題目看了答案還是邏輯錯了老半天有進步。

Code

class Solution {
    public int numIslands(char[][] grid) {
        int M = grid.length; // rows
        if (M == 0) return 0;
        int N = grid[0].length; // columns

        int count = 0;

        // 4 Directions
        List<int[]> directions = Arrays.asList( //TODO
            new int[]{0, -1},
            new int[]{0, 1},
            new int[]{-1, 0},
            new int[]{1, 0}
        );
        
        // Check every item in the grid
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                // Only check islands
                if (grid[i][j] != '1') continue;

                ++count;

                Queue<int[]> q = new LinkedList<>();

                q.add(new int[]{i, j});

                grid[i][j] = '2';

                // Start BFS
                while (!q.isEmpty()) {
                    int[] island = q.poll();
                    int x = island[0];
                    int y = island[1];

                    // Check 4 directions
                    for (int[] direction : directions) {
                        int row = x + direction[0];
                        int col = y + direction[1];

                        // Make sure the l,r,u,d are inside the grid
                        if (row < 0 || row >= M || col < 0 || col >= N)
                            continue;
                        
                        // Check island only
                        if (grid[row][col] != '1') continue;

                        q.add(new int[]{row, col});
                        
                        grid[row][col] = '2';
                    }
                }

            }
        }
        
        return count;
        
    }
}

但不知道為何runtime有點慢

討論區的寫法

看了討論區的BFS寫法，這個快了很多。他BFS是直接使用遞迴，所以不需要queue來儲存下一個要check的位置。看起來也簡潔很多，值得學習，看討論去BFS也很多用遞迴，記得每個走過的點都要標記，以免無限循環。

class Solution {
    public int numIslands(char[][] grid) {
        int count =0; // Island count
        
        // Check every position
        for(int i=0;i<grid.length;i++){
            for(int j =0;j<grid[i].length;j++){
                // Only check islands
                if(grid[i][j]== '1')
                {
                    count +=1 ;
                    call(grid,i,j); // BFS check up down left right position
                }
            }
        }
        return count;
    }

    public void call(char[][] grid, int i,int j)
    {   
        // Inside the boundary and it's indeed island
        if(i<0 || i>= grid.length || j<0 || j>= grid[i].length || grid[i][j] == '0')
        {
            return;
        }
        
        // mark visited
        grid[i][j] = '0';
        call(grid, i-1,j);
        call(grid, i+1,j);
        call(grid, i, j-1);
        call(grid, i , j+1);
    }
}

但是呢，再看了別人DFS的寫法，赫然發現，這根本就是DFS阿. . .難怪是用Recursion，用白話說就是，死命往下找，找不到才return，return的路上有更深的又會再往深處去。應該沒想錯，因為BFS之所以要用queue的原因就是這樣才有先後順序，先看完左邊再看看右邊，然後再回到左邊的children，這樣慢慢從左往右從上往下。看來討論區的那位答案應該是抄來的吧🤣幸好有發現，不然以為BFS也能Recursion做。

2024/02/03

• 有看出要用BFS或是DFS，實作卡住了，沒想到要檢查上下左右