题目

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.

分析

题目描述抽象为一个图的问题，题目本质便是求连通子图的数目。

借助图的遍历算法DFS的思想，遍历该二维矩阵，每当遇到一个‘1’计数增一，同时以该坐标为起点dfs该矩阵把相邻坐标为‘1’的元素改为非1；最终计数的结果即是连通子图数量。

AC代码

class Solution {

public:

    //等价于计算连通子图的个数

    int numIslands(vector<vector<char>>& grid) {

        if (grid.empty())

            return 0;

        //计算该二维数组的行列

        int rows = grid.size();

        int cols = grid[0].size();

        int count = 0;

        for (int i = 0; i < rows; ++i)

        {

            for (int j = 0; j < cols; ++j)

            {

                if (grid[i][j] == '1')

                {

                    ++count;

                    dfs(grid, i, j);

                }

                continue;

            }//for

        }//for

        return count;

    }

    void dfs(vector<vector<char>> &grid, int r, int c)

    {

        if (grid.empty())

            return;

        //计算该二维数组的行列

        int rows = grid.size();

        int cols = grid[0].size();

        if (r < 0 || r >= rows || c < 0 || c >= cols)

            return;

        if (grid[r][c] == '1')

        {

            //改变当前元素值为非'1'

            grid[r][c] = '2';

            dfs(grid, r, c + 1);

            dfs(grid, r + 1, c);

            dfs(grid, r, c - 1);

            dfs(grid, r - 1, c);

        }//if

        return;

    }

};

GitHub测试程序源码