Number.200——岛屿数量

题目链接：https://leetcode-cn.com/problems/number-of-islands/

题目描述：

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

示例：

输入:
11110
11010
11000
00000
输出: 1

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

这题以前在哪里做过，简单记一下思路：
题目意思就是寻找不连接在一起的1的块数，这个连接指的是上下左右四个方向相邻。
所以，很容易就想到了深度优先搜索。碰到 1 的时候开始搜索，上下左右四个方向。搜索结束条件就是上下左右任何一个方向都不是 1 了，还有边界处理。另外，还有一个节约时间的方法，就是在搜索过程中把已经搜索过的 1 换个字符代替，这样在主函数遍历的时候就不会重复搜索已经搜索过的1了。

class Solution {public int numIslands(char[][] grid) {int count = 0;for (int i = 0; i < grid.length; i++){for (int j = 0; j < grid[0].length; j++){if (grid[i][j] == '1'){dfs(grid, i, j);count++;}}}return count;}public void dfs(char[][] grid, int x, int y){if (x < 0 || x >= grid.length ||y < 0 || y >= grid[0].length || grid[x][y] != '1'){return;}grid[x][y] = '2';        // 把遍历过的1用2替换，防止多次遍历dfs(grid, x - 1, y);dfs(grid, x + 1, y);dfs(grid, x, y - 1);dfs(grid, x, y + 1);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！