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;
    }
};