200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] 的值为 '0' 或 '1'
思路
注意题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
也就是说斜角度链接是不算了， 例如示例二，是三个岛屿，如图：
这道题题目是 DFS，BFS，并查集，基础题目。
本题思路，是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。
在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
那么如果把节点陆地所能遍历到的陆地都标记上呢，就可以使用 DFS，BFS或者并查集。
深度优先搜索
以下代码使用dfs实现，如果对dfs不太了解的话，建议先看这篇题解：797.所有可能的路径，
C++代码如下：
// 版本一
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];
int 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(), m = grid[0].size();
vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
visited[i][j] = true;
result++; // 遇到没访问过的陆地，+1
dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
}
}
}
return result;
}
};
很多录友可能有疑惑，为什么 以上代码中的dfs函数，没有终止条件呢？ 感觉递归没有终止很危险。
其实终止条件 就写在了 调用dfs的地方，如果遇到不合法的方向，直接不会去调用dfs。
当然也可以这么写：
// 版本二
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) {
if (visited[x][y] || grid[x][y] == '0') return; // 终止条件：访问过的节点 或者 遇到海水
visited[x][y] = true; // 标记访问过
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过
dfs(grid, visited, nextx, nexty);
}
}
public:
int numIslands(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
result++; // 遇到没访问过的陆地，+1
dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
}
}
}
return result;
}
};
这里大家应该能看出区别了，无疑就是版本一中 调用dfs 的条件判断 放在了 版本二 的 终止条件位置上。
版本一的写法是 ：下一个节点是否能合法已经判断完了，只要调用dfs就是可以合法的节点。
版本二的写法是：不管节点是否合法，上来就dfs，然后在终止条件的地方进行判断，不合法再return。
理论上来讲，版本一的效率更高一些，因为避免了 没有意义的递归调用，在调用dfs之前，就做合法性判断。 但从写法来说，可能版本二 更利于理解一些。（不过其实都差不太多）
很多同学看了同一道题目，都是dfs，写法却不一样，有时候有终止条件，有时候连终止条件都没有，其实这就是根本原因，两种写法而已。
总结
其实本题是 dfs，bfs 模板题，但正是因为是模板题，所以大家或者一些题解把重要的细节都很忽略了，我这里把大家没注意的但以后会踩的坑 都给列出来了。
本篇我只给出的dfs的写法，大家发现我写的还是比较细的，那么后面我再单独更本题的bfs写法，虽然是模板题，但依然有很多注意的点，敬请期待！
其他语言版本
Java
下面的代码使用的是深度优先搜索 DFS 的做法。为了统计岛屿数量同时不重复记录，每当我们搜索到一个岛后，就将这个岛 “淹没” —— 将这个岛所占的地方从 “1” 改为 “0”，这样就不用担心后续会重复记录这个岛屿了。而 DFS 的过程就体现在 “淹没” 这一步中。详见代码：
public int numIslands(char[][] grid) {
int res = 0; //记录找到的岛屿数量
for(int i = 0;i < grid.length;i++){
for(int j = 0;j < grid[0].length;j++){
//找到“1”，res加一，同时淹没这个岛
if(grid[i][j] == '1'){
res++;
dfs(grid,i,j);
}
}
}
return res;
}
//使用DFS“淹没”岛屿
public void dfs(char[][] grid, int i, int j){
//搜索边界：索引越界或遍历到了"0"
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
//将这块土地标记为"0"
grid[i][j] = '0';
//根据"每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成"，对上下左右的相邻顶点进行dfs
dfs(grid,i - 1,j);
dfs(grid,i + 1,j);
dfs(grid,i,j + 1);
dfs(grid,i,j - 1);
}
//graph - dfs (和卡哥的代碼邏輯一致)
class Solution {
boolean[][] visited;
int dir[][] = {
{0, 1}, //right
{1, 0}, //down
{-1, 0}, //up
{0, -1} //left
};
public int numIslands(char[][] grid) {
int count = 0;
visited = new boolean[grid.length][grid[0].length];
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
if(visited[i][j] == false && grid[i][j] == '1'){
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][]grid, int x, int y){
if(visited[x][y] == true || grid[x][y] == '0')
return;
visited[x][y] = true;
for(int i = 0; i < 4; i++){
int nextX = x + dir[i][0];
int nextY = y + dir[i][1];
if(nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length)
continue;
dfs(grid, nextX, nextY);
}
}
}
Python:
# 版本一
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 四个方向
result = 0
def dfs(x, y):
for d in dirs:
nextx = x + d[0]
nexty = y + d[1]
if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n: # 越界了，直接跳过
continue
if not visited[nextx][nexty] and grid[nextx][nexty] == '1': # 没有访问过的同时是陆地的
visited[nextx][nexty] = True
dfs(nextx, nexty)
for i in range(m):
for j in range(n):
if not visited[i][j] and grid[i][j] == '1':
visited[i][j] = True
result += 1 # 遇到没访问过的陆地，+1
dfs(i, j) # 将与其链接的陆地都标记上 true
return result
# 版本二
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 四个方向
result = 0
def dfs(x, y):
if visited[x][y] or grid[x][y] == '0':
return # 终止条件：访问过的节点 或者 遇到海水
visited[x][y] = True
for d in dirs:
nextx = x + d[0]
nexty = y + d[1]
if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n: # 越界了，直接跳过
continue
dfs(nextx, nexty)
for i in range(m):
for j in range(n):
if not visited[i][j] and grid[i][j] == '1':
result += 1 # 遇到没访问过的陆地，+1
dfs(i, j) # 将与其链接的陆地都标记上 true
return result
# 我们用三个状态去标记每一个格子
# 0 代表海水
# 1 代表陆地
# 2 代表已经访问的陆地
class Solution:
def traversal(self, grid, i, j):
m = len(grid)
n = len(grid[0])
if i < 0 or j < 0 or i >= m or j >= n:
return # 越界了
elif grid[i][j] == "2" or grid[i][j] == "0":
return
grid[i][j] = "2"
self.traversal(grid, i - 1, j) # 往上走
self.traversal(grid, i + 1, j) # 往下走
self.traversal(grid, i, j - 1) # 往左走
self.traversal(grid, i, j + 1) # 往右走
def numIslands(self, grid: List[List[str]]) -> int:
res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
res += 1
self.traversal(grid, i, j)
return res
JavaScript
var numIslands = function (grid) {
let dir = [[0, 1], [1, 0], [-1, 0], [0, -1]]; // 四个方向
let dfs = (grid, visited, x, y) => {
for (let i = 0; i < 4; i++) {
let nextX = x + dir[i][0]
let nextY = y + dir[i][1]
if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length)
continue;
if (!visited[nextX][nextY] && grid[nextX][nextY] === "1") {
visited[nextX][nextY] = true
dfs(grid,visited,nextX,nextY)
}
}
}
let visited = new Array(grid.length).fill().map(() => Array(grid[0].length).fill(false))
let res = 0
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (!visited[i][j] && grid[i][j] === "1") {
++res;
visited[i][j] = true;
dfs(grid, visited, i, j);
}
}
}
return res
};
TypeScript
function numIslands(grid: string[][]): number {
// 四个方向
const dir: number[][] = [[0, 1], [1, 0], [-1, 0], [0, -1]];
const [m, n]: [number, number] = [grid.length, grid[0].length];
function dfs(grid: string[][], visited: boolean[][], x: number, y: number) {
for (let i = 0; i < 4; i++) {
let nextX: number = x + dir[i][0];
let nextY: number = y + dir[i][1];
// 越界了，直接跳过
if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) {
continue;
}
// 没有访问过同时是陆地
if (!visited[nextX][nextY] && grid[nextX][nextY] === '1') {
visited[nextX][nextY] = true;
dfs(grid, visited, nextX, nextY);
}
}
}
const visited: boolean[][] = Array.from({ length: m }, _ => new Array(n).fill(false));
let result: number = 0;
for (let i = 0; i < m; i++) {
for (let k = 0; k < n; k++) {
if (!visited[i][k] && grid[i][k] === '1') {
++result; // 遇到没访问过的陆地，+1
visited[i][k] = true;
dfs(grid, visited, i, k); // 将与其链接的陆地都标记上 true
}
}
}
return result;
}
Go
var DIRECTIONS = [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
func numIslands(grid [][]byte) int {
res := 0
visited := make([][]bool, len(grid))
for i := 0; i < len(grid); i++ {
visited[i] = make([]bool, len(grid[0]))
}
for i, rows := range grid {
for j, v := range rows {
if v == '1' && !visited[i][j] {
res++
dfs(grid, visited, i, j)
}
}
}
return res
}
func dfs(grid [][]byte, visited [][]bool, i, j int) {
visited[x][y] = true
for _, d := range DIRECTIONS {
x, y := i+d[0], j+d[1]
if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) {
continue
}
if grid[x][y] == '1' && !visited[x][y] {
dfs(grid, visited, x, y)
}
}
}
Rust:
impl Solution {
const DIRECTIONS: [(i32, i32); 4] = [(0, 1), (1, 0), (-1, 0), (0, -1)];
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
let mut visited = vec![vec![false; grid[0].len()]; grid.len()];
let mut res = 0;
for (i, chars) in grid.iter().enumerate() {
for (j, &c) in chars.iter().enumerate() {
if !visited[i][j] && c == '1' {
res += 1;
Self::dfs(&grid, &mut visited, (i as i32, j as i32));
}
}
}
res
}
pub fn dfs(grid: &Vec<Vec<char>>, visited: &mut Vec<Vec<bool>>, (x, y): (i32, i32)) {
for (dx, dy) in Self::DIRECTIONS {
let (nx, ny) = (x + dx, y + dy);
if nx < 0 || nx >= grid.len() as i32 || ny < 0 || ny >= grid[0].len() as i32 {
continue;
}
let (nx, ny) = (nx as usize, ny as usize);
if grid[nx][ny] == '1' && !visited[nx][ny] {
visited[nx][ny] = true;
Self::dfs(grid, visited, (nx as i32, ny as i32));
}
}
}
}