Number of Islands -- leetcode

Number of Islands -- leetcode

Given a 2d grid map of '1's (land) and '0's (water), count 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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

基本思路：

1.遍歷二維數組每個元素

2. 如果發現其為 '1'， 則發現了一塊島嶼，島嶼數量+1， 並從此點進行深度優先遍歷，將該島嶼所有元素置上訪問標記。

遞歸遍歷，即是向上、下、左、右，都進行訪問。直到邊界或者遇到水（'0'）、已訪問（'2）'為止。

3. 最後將訪問標記恢復為'1'。此步為可選，不恢復，leetcode也不會報錯。

class Solution {
public:
    int numIslands(vector>& grid) {
        int ans = 0;
        if (grid.empty() || grid[0].empty())
            return ans;
        
        const int m = grid.size();
        const int n = grid[0].size();
        for (int i=0; i >&grid, int i, int j) {
        if (j < 0 || i < 0 || 
            i == grid.size() || 
            j == grid[0].size() ||
            grid[i][j] != '1')
            return;
        
        grid[i][j] = '2';
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
};