Number of Islands

文章目录

1. Number of Islands
1. 1.1. 问题描述
2. 1.2. 解法

问题描述

在一个二维的地图上，有陆地(1)和水(0)，我们要数整个地图上有多少个小岛。那么什么是小岛呢？陆地的上下左右都是水(0)，那么这个陆地就是小岛。在这个地图的四周也都是水

比如：

有1个小岛

有3个小岛

解法

这个问题其实就是在求平面无向图上的强连通分量个数。我们可以用深度优先算法来遍历所有的连通分量，遍历过的节点就标识为”visited”。这里有个技巧，因为题目中的小岛是vector<vector>类型的，也就是我们不需要额外的空间来记录访问过的节点，只需要将该陆地变为2来表示这个陆地已经访问过了。