【力扣刷题练习】200. 岛屿数量

题目描述：

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

题目解答：

class Solution {
private:
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0],nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 ||nexty >= grid[0].size())
                continue; // 越界了，直接跳过
            if (!visited[nextx][nexty] &&
                grid[nextx][nexty] == '1') {
                visited[nextx][nexty] = true;
                dfs(grid, visited, nextx, nexty);
            }
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();    //行数
        int m = grid[0].size(); //列数
        vector<vector<bool>> v = vector<vector<bool>>(
            n, vector<bool>(m, false)); // n行m列，初始化为false
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!v[i][j] && grid[i][j] == '1') {
                    count++;
                    dfs(grid, v, i, j);
                }
            }
        }
        return count;
    }
};

题目思路：

预定义方向数组：dir数组存储了四个方向上的行和列的偏移量。这个数组用来在深度优先搜索(DFS)时确定下一个要检查的陆地的位置。

深度优先搜索 (DFS)：dfs递归在给定的网格中搜索岛屿。它从给定的(x, y)位置开始，如果该位置是陆地（值为’1’），则标记为已访问，并递归地搜索其四个相邻的陆地位置。如果这四个相邻位置中有任何一个是新的陆地（未被访问且值为’1’），则再次调用dfs函数。

计算岛屿数量：在numIslands函数中，首先创建一个大小与输入网格相同的二维布尔数组，并初始化所有元素为false，用来表示哪些陆地已被访问过。然后，它遍历输入的网格，如果找到一个新的未访问过的陆地（值为’1’），则将该陆地的计数增加1，并调用dfs函数来访问并标记该陆地及其所有相邻的陆地。