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

雨点打透心脏的1/2处 2022-06-08 08:24 197阅读 0赞

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 + 矩阵遍历][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);
                }
            }
        }
    };

[leetcode 130. Surrounded Regions DFS _]: http://blog.csdn.net/jackzhang_123/article/details/78002839