您当前位置：首页 > php开源 > php教程 > [LeetCode] Number of Islands

[LeetCode] Number of Islands

来源：程序员人生发布时间：2015-06-04 08:12:49 阅读次数：2565次

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:

Answer: 1

Example 2:

Answer: 3

解题思路

深度优先搜索，要求的结果就是图中连通份量的个数。更详细的思路可以参考Find the number of islands。

实现代码

//Runtime:13ms
class Solution {
public:
    int numIslands(vector<vector<char>> &grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int row = grid.size();
        int col = grid[0].size();
        int cnt = 0;
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (grid[i][j] == '1')
                {
                    cnt++;
                    dfs(grid, i, j);
                }
            }
        }

        return cnt;
    }

private:
    void dfs(vector<vector<char>> &grid, int row, int col)
    {
        if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] != '1')
        {
            return;
        }

        grid[row][col] = 'X';
        dfs(grid, row, col + 1);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row - 1, col);
    }
};

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 IOS ---网络异步请求

下一篇 C++数组。

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点