查询小岛的个数

查询小岛的个数，引申剑值offer13:机器人的运动范围和剑值offer47:礼物的最大价值

题目

有一个二维数组，由0和1组成。比如：
a[][] = {{1,0,0,1,1},{1,1,0,0,0},{1,0,1,0,1},{0,0,1,1,1},{1,1,0,0,0}}
所有1如果“上下左右”可以联通的，则认为是1个小岛，注意斜对角线的1不算联通。像上面的二维数组，一共对应4个小岛。
输入

{{1,0,0,1,1},
{1,1,0,0,0},
{1,0,1,0,1},
{0,0,1,1,1},
{1,1,0,0,0}}

输出

4

解题思路

1. 构造一个相同维数的数组visited，用来记录是否访问过该点坐标。初始化数组为全零。如果访问过该点坐标则置为1，否则为0。
2. 如何判断上下左右相连的1属于一个小岛: 采用递归对每个坐标点的上下左右四个方向进行判断是否为1，同时设置标志位。在判断每个方向时设置flag来证明是否可以相连。

代码

class Solution{
    public:
        void isLandCore(int Land[][cols],int row,int col,int visited[][cols], bool & flag)
        {
            if(visited[row][col] == 0 && Land[row][col]==1)
            {
                flag = true;  // 代表这是一个小岛
                visited[row][col] = 1;
                //判断是否有相连的小岛
                bool tmp = false;
                if(row > 0)
                {
                    isLandCore(Land,row-1,col,visited, tmp);//每次判断一个点是否为小岛时tmp都为false
                }
                if(row < rows-1)
                {
                    isLandCore(Land,row+1,col,visited, tmp);
                }

                if(col > 0)
                {
                    isLandCore(Land,row,col-1,visited, tmp);
                }

                if(col < cols-1)
                {
                    isLandCore(Land,row,col+1,visited, tmp);
                }
            }
        }
        int isLand(int Land[][cols])
        {
            if(Land == NULL)
            {
                return 0;
            }
            int count = 0;
            bool flag;
            int visited[rows][cols];
            memset(visited,0,sizeof(int)*rows*cols);
            for(int i=0; i < rows; ++i)
            {
               for(int j=0; j < cols; ++j)
               {
                   flag = false;
                   isLandCore(Land, i, j, visited, flag);
                   if(true == flag)
                   {
                       ++count; 
                   }
               }
            }
            return count;
        }
};

延伸

若相求总共的小岛面积，怎么做？
把每次遇到1的坐标进行累加

class Solution{
    public:
        int isLandCore(int Land[][cols],int row,int col,int visited[][cols], bool & flag)
        {
            int a[4];
            int result = 0;
           memset(a,0,4*sizeof(int));
            if(visited[row][col] == 0 && Land[row][col]==1)
            {
                flag = true;  // 代表这是一个小岛
                visited[row][col] = 1;
                //判断是否有相连的小岛
                bool tmp = false;
                if(row > 0)
                {
                    a[0] = isLandCore(Land,row-1,col,visited, tmp);//每次判断一个点是否为小岛时tmp都为false
                }
                if(row < rows-1)
                {
                    a[1] = isLandCore(Land,row+1,col,visited, tmp);
                }

                if(col > 0)
                {
                    a[2] = isLandCore(Land,row,col-1,visited, tmp);
                }

                if(col < cols-1)
                {
                    a[3] = isLandCore(Land,row,col+1,visited, tmp);
                }
                result = 1 + a[0] + a[1] + a[2] + a[3];
            }
            return result;
        }
        int isLand(int Land[][cols])
        {
            if(Land == NULL)
            {
                return 0;
            }
            int count = 0,sum = 0;
            bool flag;
            int visited[rows][cols];
            memset(visited,0,sizeof(int)*rows*cols);
            for(int i=0; i < rows; ++i)
            {
               for(int j=0; j < cols; ++j)
               {
                   flag = false;
                   sum += isLandCore(Land, i, j, visited, flag);
                   if(true == flag)
                   {
                       ++count; 
                   }
               }
            }
            return sum;
        }
};

完整c++代码见Github