LeetCode 200. Number of Islands

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:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

解析：给定的矩阵由0和1组成，1表示岛屿，0表示水，计算岛屿的数量。这个题目实际是计算连续区域的数量。采用深度优先遍历，同时采用二维数组来记录当前位置是否被访问过。用res记录数量，采用两层循环，如果当前位置是0或者被访问过则跳过，否则进入dfs处理，依次遍历上下左右4个位置，直到遇到0没法继续遍历，则返回，此时res+1，最终获取到岛屿数量。具体代码如下：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty() || grid[0].empty())
            return 0;
        int m = grid.size();
        int n = grid[0].size();
        int res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        for(int i =0; i < m; i++)
            for(int j =0; j < n; j++)
            {
                if(grid[i][j] == '0' || visited[i][j])
                    continue;
                dfs(grid, visited, i, j);
                res ++;
            }
        return res;
    }
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y)
    {
        if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y])
            return;
        visited[x][y] = true;
        dfs(grid, visited, x-1, y);
        dfs(grid, visited, x+1, y);
        dfs(grid, visited, x, y-1);
        dfs(grid, visited, x, y+1);
    }
};