# 200. Number of Islands

Given a 2d grid map of `'1'`s (land) and `'0'`s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

``````Input:
11110
11010
11000
00000

Output: 1
``````

Example 2:

``````Input:
11000
11000
00100
00011

Output: 3
``````

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<bool>> visited(m, vector<bool>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0' || visited[i][j]) continue;
helper(grid, visited, i, j);
++res;
}
}
return res;
}
void helper(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) return;
visited[x][y] = true;
helper(grid, visited, x - 1, y);
helper(grid, visited, x + 1, y);
helper(grid, visited, x, y - 1);
helper(grid, visited, x, y + 1);
}
};
``````

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<bool>> visited(m, vector<bool>(n));
vector<int> dirX{-1, 0, 1, 0}, dirY{0, 1, 0, -1};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0' || visited[i][j]) continue;
++res;
queue<int> q{{i * n + j}};
while (!q.empty()) {
int t = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
int x = t / n + dirX[k], y = t % n + dirY[k];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '0' || visited[x][y]) continue;
visited[x][y] = true;
q.push(x * n + y);
}
}
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/200

Number of Islands II

Surrounded Regions

Walls and Gates

Max Area of Island

https://leetcode.com/problems/number-of-islands/

https://leetcode.com/problems/number-of-islands/discuss/56589/C%2B%2B-BFSDFS

https://leetcode.com/problems/number-of-islands/discuss/56359/Very-concise-Java-AC-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation