C++:岛屿个数问题

alt

采用DFS方式,对二维数据进行遍历,遇到1则找到一个岛屿,然后把与之关联的位置全部置为2,那么对二维数组完成一次遍历,即可得出结果
/*************************************************************************
	> File Name: 11.cpp
	> Author: ryan_naiquan
	> Mail: ryan_naiquan@163.com 
	> Created Time: Fri 02 Aug 2019 05:11:31 PM CST
 ************************************************************************/

#include <iostream>
#include <vector>

using namespace std;


void setOne(vector<vector<int>> &grid,int row,int col)
{
    int m=grid.size();
    int n=grid[0].size();
    if((row<0)||(row>=m)||(col<0)||(col>=n)||(grid[row][col]!=1))
    {
            return;
    }
    grid[row][col]=2;
    setOne(grid,row+1,col);
    setOne(grid,row-1,col);
    setOne(grid,row,col+1);
    setOne(grid,row,col-1);
}
int numIslands(vector<vector<int>>& grid) 
{
    int m=grid.size();
    if(m==0) return 0;
    int n=grid[0].size();
    if(n==0) return 0;
    int sum=0;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(grid[i][j]==1)
            {
                sum++;
                setOne(grid,i,j);
            }
        }
    }
    cout << sum << endl;
    return sum;
}

int main()
{
	std::vector<std::vector<int>> v(3,std::vector<int>(3));
	for (int i = 0; i <3; i++)
        for (int j = 0; j <3; j++)
            v[i][j] = (1);
       numIslands(v);   
	return 0;
}

暂无评论
发表新评论