leetcode 200. Number of Islands 十分典型的DFS深度优先遍历-蒲公英云

leetcode 200. Number of Islands 十分典型的DFS深度优先遍历

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的数量，也就是岛屿的数量，这就是一个简单的DFS深度优先遍历应用，和这一道题leetcode 130. Surrounded Regions DFS + 矩阵遍历，基本一致，值得学习。

这是一个十分典型的DFS深度优先遍历的样例，值得学习！

代码如下：

public class Solution 
{
    public int numIslands(char[][] grid) 
    {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int count = 0;
        for (int i = 0; i < grid.length; i++)
        {
            for (int j = 0; j < grid[0].length; j++)
            {
                if (grid[i][j] == '1') 
                {
                    count++;
                    dfsSearch(grid, i, j);
                }
            }
        }
        return count++;
    }
    // 每遇到'1'后, 开始向四个方向 递归搜索. 搜到后变为'0',
    // 因为相邻的属于一个island. 然后开始继续找下一个'1'.
    private void dfsSearch(char[][] grid, int i, int j)
    {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length 
            || grid[i][j] != '1')
            return;
        // 也可以才用一个visited数组，标记遍历过的岛屿
        grid[i][j] = '0';
        dfsSearch(grid, i + 1, j);
        dfsSearch(grid, i - 1, j);
        dfsSearch(grid, i, j + 1);
        dfsSearch(grid, i, j - 1);
    }
}

下面是C++的做法，就是一个很简单的DFS深度优先遍历的简单应用

代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int numIslands(vector<vector<char>>& g) 
    {
        int count = 0;
        if (g.size() <= 0)
            return count;
        vector<vector<bool>> visit(g.size(),vector<bool>(g[0].size(),false));
        for (int i = 0; i < g.size(); i++)
        {
            for (int j = 0; j < g[0].size(); j++)
            {
                if (g[i][j] == '1' && visit[i][j] == false)
                {
                    getAll(g, visit, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    void getAll(vector<vector<char>>& g, vector<vector<bool>>& visit, int x, int y)
    {
        if (x < 0 || x >= g.size() || y < 0 || y >= g[0].size())
            return;
        else
        {
            if (g[x][y] == '1' && visit[x][y]==false)
            {
                visit[x][y] = true;
                getAll(g, visit, x - 1, y);
                getAll(g, visit, x + 1, y);
                getAll(g, visit, x, y + 1);
                getAll(g, visit, x, y - 1);
            }
        }
    }
};