## Approach 1: BFS

• Time:O(mn)
• Space:O(\min(m, n))

## C++

class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
int ans = 0;

auto bfs = [&](int r, int c) {
queue<pair<int, int>> q{{{r, c}}};
grid[r][c] = '2';  // mark '2' as visited
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] != '1')
continue;
q.emplace(x, y);
grid[x][y] = '2';  // mark '2' as visited
}
}
};

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == '1') {
bfs(i, j);
++ans;
}

return ans;
}
};

## JAVA

class Solution {
public int numIslands(char[][] grid) {
int ans = 0;

for (int i = 0; i < grid.length; ++i)
for (int j = 0; j < grid[0].length; ++j)
if (grid[i][j] == '1') {
bfs(grid, i, j);
++ans;
}

return ans;
}

private static final int[] dirs = {0, 1, 0, -1, 0};

private void bfs(char[][] grid, int r, int c) {
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[] {r, c});
grid[r][c] = '2'; // mark '2' as visited
while (!q.isEmpty()) {
final int i = q.peek()[0];
final int j = q.poll()[1];
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == grid.length || y < 0 || y == grid[0].length)
continue;
if (grid[x][y] != '1')
continue;
q.offer(new int[] {x, y});
grid[x][y] = '2'; // mark '2' as visited
}
}
}
}

## Python

class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])
dirs = [0, 1, 0, -1, 0]

def bfs(r, c):
q = deque([(r, c)])
grid[r][c] = '2'  # mark '2' as visited
while q:
i, j = q.popleft()
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if grid[x][y] != '1':
continue
q.append((x, y))
grid[x][y] = '2'  # mark '2' as visited

ans = 0

for i in range(m):
for j in range(n):
if grid[i][j] == '1':
bfs(i, j)
ans += 1

return ans

• Time:O(mn)
• Space:O(mn)

## C++

class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int ans = 0;

for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[0].size(); ++j)
if (grid[i][j] == '1') {
dfs(grid, i, j);
++ans;
}

return ans;
}

private:
void dfs(vector<vector<char>>& grid, int i, int j) {
if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
return;
if (grid[i][j] != '1')
return;

grid[i][j] = '2';  // mark '2' as visited
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
};

## JAVA

class Solution {
public int numIslands(char[][] grid) {
int ans = 0;

for (int i = 0; i < grid.length; ++i)
for (int j = 0; j < grid[0].length; ++j)
if (grid[i][j] == '1') {
dfs(grid, i, j);
++ans;
}

return ans;
}

private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
return;
if (grid[i][j] != '1')
return;

grid[i][j] = '2'; // mark '2' as visited
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}

## Python

class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])

def dfs(i: int, j: int) -> None:
if i < 0 or i == m or j < 0 or j == n:
return
if grid[i][j] != '1':
return

grid[i][j] = '2'  # mark '2' as visited
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)

ans = 0

for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
ans += 1

return ans