200. Number of Islands

DFS，时间复杂度O(m * n)，数据过大栈有限制。

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;

    int count = 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);
                count++;
            }
        }
    }
    return count;
}

public void record(char[][] grid, int i, int j) {
    if (i >= grid.length || i < 0 || j >= grid[0].length || j < 0 || grid[i][j] == '0') return;
    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

最好另外设置一个visited数组，并且简化dfs写法，注意下和79. Word Search不同的地方（不用将visited复原，因为是求一整块地方）

private static final int[][] distance = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static boolean[][] visited;

public static int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

    visited = new boolean[grid.length][grid[0].length];
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (!visited[i][j] && grid[i][j] == '1') {
                searchIslands(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private static void searchIslands(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || visited[i][j] || grid[i][j] != '1') return;
    visited[i][j] = true;
    for (int k = 0; k < 4; k++) {
        int newX = i + distance[k][0];
        int newY = j + distance[k][1];
        searchIslands(grid, newX, newY);
    }
}

BFS

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int count = 0;
    Queue<Integer> queue = new LinkedList<>();
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int row = grid.length; 
    int col = grid[0].length;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (grid[i][j] == '1') {
                count++;
                grid[i][j] = '0';
                queue.offer(i * col + j);

                while (!queue.isEmpty()) {
                    int curNode = queue.poll();
                    int x = curNode / col;
                    int y = curNode % col;
                    for (int k = 0; k < 4; k++) {
                        int newx = x + dx[k];
                        int newy = y + dy[k];
                        if (newx < 0 || newx >= row || newy < 0 || newy >= col || grid[newx][newy] != '1')
                            continue;
                        grid[newx][newy] = '0';
                        queue.offer(newx * col + newy);
                    }
                }
            }
        }
    }
    return count;

一道面试题，斜对角也算连通，并且计算最大个数。

import java.util.Arrays;
import java.util.Scanner;

public class Team {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        in.useDelimiter("[,\n]"); // use comma and newline delimiter
        int row = in.nextInt(), col = in.nextInt();
        char[][] board = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                board[i][j] = in.next().charAt(0);
            }
        }
        in.close();
        System.out.println("Input row: " + row + " col: " + col);
        System.out.println(Arrays.deepToString(board));
        numberOfTeam(board);
    }

    public static void numberOfTeam(char[][] board) {
        if (board == null || board.length == 0) return;
        int count = 0;
        int depth = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '1') {
                    depth = Math.max(depth, dfs(board, i, j));
                    count++;
                }
            }
        }
        System.out.println("The number of the team: " + count);
        System.out.println("The number of people in the largest team: " + depth);
        System.out.println(count + "," + depth);
    }

    public static int dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '0') return 0;
        board[i][j] = '0';
        return 1 + dfs(board, i + 1, j)
                + dfs(board, i - 1, j)
                + dfs(board, i, j + 1)
                + dfs(board, i, j - 1)
                + dfs(board, i + 1, j + 1)
                + dfs(board, i + 1, j - 1)
                + dfs(board, i - 1, j + 1)
                + dfs(board, i - 1, j - 1);
    }
    //test case, 6, 8
//            10,10
//            0,0,0,0,0,0,0,0,0,0
//            0,0,0,1,1,0,1,0,0,0
//            0,1,0,0,0,0,0,1,0,1
//            1,0,0,0,0,0,0,0,1,1
//            0,0,0,1,1,1,0,0,0,1
//            0,0,0,0,0,0,1,0,1,1
//            0,1,1,0,0,0,0,0,0,0
//            0,0,0,1,0,1,0,0,0,0
//            0,0,1,0,0,1,0,0,0,0
//            0,1,0,0,0,0,0,0,0,0
}