public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
int[][] directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
searchByBFS(grid, i, j, m, n, directions);
public void searchByBFS(char[][] grid, int row, int col, int m, int n, int[][] directions) {
Queue<Integer> queue = new LinkedList<>();
queue.add(row * n + col);
while (!queue.isEmpty()) {
int curPoint = queue.remove();
int curRow = curPoint / n;
int curCol = curPoint % n;
for (int[] direction : directions) {
int nextRow = curRow + direction[0];
int nextCol = curCol + direction[1];
if (isValid(grid, nextRow, nextCol)) {
grid[nextRow][nextCol] = '0';
queue.add(nextRow * n + nextCol);
public boolean isValid(char[][] grid, int row, int col) {
return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == '1';