mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
39 lines
1.2 KiB
Markdown
39 lines
1.2 KiB
Markdown
![]() |
# [200. Number of Islands](https://leetcode.com/problems/number-of-islands/)
|
||
|
# 思路
|
||
|
求岛屿数量. 简单用DFS或者BFS就可以了. 下面代码用的DFS.
|
||
|
|
||
|
> 亲测visited数组定义成bool型要比定义成int型慢不少.
|
||
|
|
||
|
# C++
|
||
|
``` C++
|
||
|
class Solution {
|
||
|
private:
|
||
|
vector<int>dx{-1, 1, 0, 0}; // 上下左右四个方向
|
||
|
vector<int>dy{0, 0, -1, 1};
|
||
|
void DFS(int i, int j, const vector<vector<char>>& grid, vector< vector<int>>& visited){
|
||
|
if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) return;
|
||
|
if(visited[i][j] || grid[i][j] == '0') return;
|
||
|
|
||
|
visited[i][j] = 1;
|
||
|
for(int k = 0; k < 4; k++)
|
||
|
DFS(i + dx[k], j + dy[k], grid, visited);
|
||
|
}
|
||
|
public:
|
||
|
int numIslands(vector<vector<char>>& grid) {
|
||
|
int m = grid.size(), res = 0;
|
||
|
if(!m) return 0;
|
||
|
int n = grid[0].size();
|
||
|
|
||
|
vector< vector<int>>visited(m, vector<int>(n, 0)); // int比bool型数组快
|
||
|
for(int i = 0; i < m; i++){
|
||
|
for(int j = 0; j < n; j++){
|
||
|
if(visited[i][j] || grid[i][j] == '0') continue;
|
||
|
DFS(i, j, grid, visited);
|
||
|
res++;
|
||
|
}
|
||
|
}
|
||
|
return res;
|
||
|
}
|
||
|
};
|
||
|
```
|