C++：岛屿个数问题

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

本文由 Ryan 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2020/05/07 15:17