# bfs and dfs

• ``````class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int max_area = 0;

for (int i = 0; i != grid.size(); i++) {
for (int j = 0; j != grid[0].size(); j++) {
if (grid[i][j] == 1) {
max_area = max(max_area, isLand_bfs(grid, i, j));
}
}
}
return max_area;
}

// dfs就是单纯的递归就好了(递归时间开销明显大)
int isLand_dfs(vector<vector<int>>& grid, int i, int j) {
if (i >= 0 && j >= 0 && i < grid.size() && j < grid[0].size() && grid[i][j] == 1) {
grid[i][j] = 2;  // 直接将原始数组改变，设置为2避免了重复（包括maxAreaOfIsland函数中的重复）
return 1 + isLand_dfs(grid, i - 1, j) + isLand_dfs(grid, i + 1, j) + isLand_dfs(grid, i, j - 1) + isLand_dfs(grid, i, j + 1);
}
return 0;
}

// bfs需要设置一个队列进行循环，不需要递归
int isLand_bfs(vector<vector<int>>& grid, int i, int j) {
int area = 0;
queue<pair<int, int>> point;
point.push({i, j});

while (!point.empty()) {
int x = point.front().first, y = point.front().second;
point.pop();
if (x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size() && grid[x][y] == 1) {
grid[x][y] = 2;
area++;
point.push({x - 1, y});
point.push({x + 1, y});
point.push({x, y - 1});
point.push({x, y + 1});
}
}

return area;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.