dfs
class Solution {
public:
vector<vector<int>> g;
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dfs(int x, int y) {
g[x][y] = 0;
int res = 1;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b])
res += dfs(a, b);
}
return res;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
g = grid;
n = g.size(), m = g[0].size();
int res = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j]) {
res = max(res, dfs(i, j));
}
return res;
}
};
bfs
class Solution {
public:
#define xa first
#define ya second
typedef pair<int, int> PII;
int n, m;
vector<vector<int>> res;
vector<vector<int>> g;
queue<PII> q;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int bfs(int x, int y) {
int cnt = 0;
q.push({x, y});
g[x][y] = 0;
while (q.size()) {
auto t = q.front();
cnt ++ ;
q.pop();
for (int i = 0; i < 4; i ++ ) {
int a = t.xa + dx[i], b = t.ya + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (g[a][b] == 0) continue;
g[a][b] = 0;
q.push({a, b});
}
}
return cnt;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size();
g = grid;
int res = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 1) {
res = max(res, bfs(i, j));
}
return res;
}
};
```