# Leetcode [No. 200] Number of Islands (MEDIUM) 解題心得

+ Blind 169 Challenge solved on 2024/02/13

聽說這題是某年群暉intern出現過的白板題，一次過超開心><

+ Neetcode150 Challenge solved on 2025/02/19 (Solve second times)

## 題目

https://leetcode.com/problems/number-of-islands/description/

## 思路
+ 這個解法就是用DFS去traverse grid上每一個(x,y)
+ 為了去確保每個island都走過了，我們需要O(n^2)的複雜度來iterate檢查每一個節點。
+ 當我們找到了一個"1"，我們就去對那個點做DFS，把DFS走過的點都存起來(visited)

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        // use DFS to traverse every pos in grid.
        int cnt = 0;
        vector<vector<bool>> visited(grid.size(), vector<bool> (grid[0].size(), false));
        for(int i = 0 ; i < grid.size(); i++)
        {
            for(int j = 0 ; j < grid[i].size(); j++)
            {
                if(!visited[i][j] && grid[i][j] != '0')
                {
                    DFS(grid, visited, i,j);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    void DFS(vector<vector<char>>& grid, vector<vector<bool>>& visited, int row, int col)
    {
        if(grid[row][col] == '1' && !visited[row][col])
        {
            visited[row][col] = true;
            if(row+1 < grid.size())
            {
                DFS(grid, visited, row+1, col);
            }
            if(col+1 < grid[0].size())
            {
                DFS(grid, visited, row, col+1);
            }
            if(row-1 >= 0)
            {
                DFS(grid, visited, row-1, col);
            }
            if(col-1 >= 0)
            {
                DFS(grid, visited, row, col-1);
            }
        }
        return;
    }
};

### 解法分析
+ time complexity: O(n＊m)

### 執行結果

---

## 第二次挑戰

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        int cnt = 0;
        for (int i = 0 ; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    dfs(i, j, grid, visited);     
                    cnt++;
                }
            }
        }
        return cnt;
    }
    void dfs(int r, int c, vector<vector<char>>& grid, vector<vector<bool>>& visited)
    {
        if (visited[r][c] == true) return;

        visited[r][c] = true;
        if (r + 1 < grid.size() && grid[r+1][c] == '1') {
            dfs(r + 1, c, grid, visited);
        }
        if (r - 1 >= 0 && grid[r-1][c] == '1') {
            dfs(r - 1, c, grid, visited);
        }
        if (c + 1 < grid[0].size() && grid[r][c+1] == '1') {
            dfs(r, c + 1, grid, visited);
        }
        if (c - 1 >= 0 && grid[r][c-1] == '1') {
            dfs(r, c - 1, grid, visited);
        }

    }
};