c++求岛屿数量

1.问题描述

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
例如：
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]

2.源码实现

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct point {
    int x;
    int y;
};

int get_next(vector<vector<char>> &map, int n, int m, int *x, int *y)
{
    if(*x - 1 >= 0 && map[*x-1][*y] == '1')
    {
        map[*x-1][*y] = '0';

        *x = (*x-1);

        return 0;
    }

    if(*x + 1 < n && map[*x+1][*y] == '1')
    {
        map[*x+1][*y] = '0';

        *x = (*x+1);

        return 0;
    }

    if(*y - 1 >= 0 && map[*x][*y-1] == '1')
    {
        map[*x][*y-1] = '0';

        *y = (*y-1);

        return 0;
    }

    if(*y + 1 < m && map[*x][*y+1] == '1')
    {
        map[*x][*y+1] = '0';

        *y = (*y+1);

        return 0;
    }

    return -1;
}

int get_one(vector<vector<char>> &map, int n, int m, int x, int y)
{
    stack<struct point> s;
    struct point a;

    if(map[x][y] == '0')
    {
        return 0;
    }

    a.x = x;
    a.y = y;

    s.push(a);

    while(!s.empty())
    {
        a = s.top();

        x = a.x;
        y = a.y;

        if(get_next(map, n, m, &x, &y) == 0)
        {
            a.x = x;
            a.y = y;

            s.push(a);
        }
        else
        {
            s.pop();
        }
    }

    return 1;
}

int get_num(vector<vector<char>> &map)
{
    int n, m;
    int i, j, k = 0;

    n = map.size();
    m = map[0].size();

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            k += get_one(map, n, m, i, j);
        }
    }

    return k;
}

int main()
{
    vector<vector<char>> map = {{'1','1','0','0','0'}, {'0','1','0','1','1'}, {'0','0','0','1','1'}, {'0','0','0','0','0'}, {'0','0','1','1','1'}};
    int i;

    printf("%d\n", get_num(map));

    return 0;
}

3.编译源码

$ g++ -o test test.cpp -std=c++11

4.运行及其结果

$ ./test
3