岛屿数量

问题描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:
输入:
11110
11010
11000
00000

输出: 1

示例 2:
输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands

思路

最开始的时候，将所有的小岛的 访问位 置为0；
i从0到grid.size(),j从0到grid[0].size()遍历，如果vis[i][j] && grid[i][j] == '1' 将visi置为true;将其邻接位置的1的 访问位 置为0；
返回结果ans++；
最后返回ans即可。

题解

class Solution {
public:
    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, n, m, ans = 0;
    vector<vector<bool>> vis;
    bool check(int x, int y, const vector<vector<char>> &grid) {
        return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1' && !vis[x][y];
    }
    void dfs(int x, int y, const vector<vector<char>> &grid) {
        vis[x][y] = true;
        for (int k = 0; k < 4; k++) {
            if (check(x + next[k][0], y + next[k][1], grid)) dfs(x + next[k][0], y + next[k][1], grid);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        n = grid.size(), m = grid[0].size();
        vis.resize(n);
        for (int i = 0; i < n; i++) vis[i].resize(m, false);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j] && grid[i][j] == '1') {
                    dfs(i, j, grid);
                    ans++;
                }
            }
        }
        return ans;
    }
};