200. Number of Islands

Description

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.

Examples

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

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

思路

使用 for 回全檢查每一格，如果是　1 便進入 dfs，此 dfs 的功能會是將 1 的島嶼清為 0 ，這樣回到 for 迴圈便不會再次檢查到。
這邊需要注意的是 if (row < 0 || col < 0 || row >= mrow || col >= mcol ||grid[row][col] == '0') 中 grid[row][col] == '0' 要放在最後一個 or 比較，我一開始放在前面它會超出 grid 產生錯誤。

C++

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int row, int col, int *mrow, int *mcol) {
        if (row < 0 || col < 0 || row >= *mrow || col >= *mcol ||
            grid[row][col] == '0')
            return;

        grid[row][col] = '0';

        dfs(grid, row + 1, col, mrow, mcol);
        dfs(grid, row, col + 1, mrow, mcol);
        dfs(grid, row - 1, col, mrow, mcol);
        dfs(grid, row, col - 1, mrow, mcol);
        return;
    }

    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        int maxrow = grid.size();
        int maxcol = grid[0].size();
        for (int i = 0; i < maxrow; i++) {
            for (int j = 0; j < maxcol; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, &maxrow, &maxcol);
                    count++;
                }
            }
        }
        return count;
    }
};