LeetCode: 200. Number of Islands

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

解题思路

依次遍历每一个格子,如果该格子是 1,则深度优先搜索将和它相连的为 1 的格子都标记为 0

AC 代码

class Solution 
{
    void dfsWithFlag(vector<vector<char>>& grid, int i, int j)
    {
        if(i < 0 || i >= grid.size() || j < 0 || j >= grid[i].size() || grid[i][j] == '0')
        {
            return ;
        }
        else
        {
            grid[i][j] = '0';
        }

        const static int dirs[][2] = 
            {
                {0,  1}, // 下
                {0, -1}, // 上
                {1,  0}, // 右
                {-1, 0}, // 左
            };

        for(int k = 0; k < 4; ++k)
        {
            int tx = i + dirs[k][0];
            int ty = j + dirs[k][1];

            dfsWithFlag(grid, tx, ty);
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) 
    {
        int cnt = 0;

        for(int i = 0; i < grid.size(); ++i)
        {
            for(int j = 0; j < grid[i].size(); ++j)
            {
                if(grid[i][j] == '1')
                {
                    ++cnt;
                    dfsWithFlag(grid, i, j);
                }
            }
        }

        return cnt;
    }
};
全部评论

相关推荐

怎么起名字:早知道就不读书了,害得我送外卖还得扶眼镜
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
求offer的大角牛:不吃香菜
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务