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