LeetCode 200. Number of Islands [Medium] [C++] 解題筆記

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

想法:

    這題就是單純的 DFS 或是 BFS 就可以解了，遍歷整個二維陣列當遇到 "1" 的時候便從該點開始 DFS 或 BFS 把

相連的位置都找出來並標記成 "0" 即可。

完整程式碼:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0) { return 0; }
        int ans = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                ans += grid[i][j] - '0';
                dfs(grid, i, j); 
            }   
        }   
    
        return ans;
    }   
    void dfs(vector<vector<char>>& grid, int i, int j) {
        // out of map
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {
            return;
        }   
        grid[i][j] = '0';
        dfs(grid, i - 1, j); 
        dfs(grid, i + 1, j); 
        dfs(grid, i, j - 1); 
        dfs(grid, i, j + 1); 
    }   
};