1. How to create 2d array/list in Python efficiently?

    1
    2
    3
    4
    5
    6
    7
    8
    >>> A = [[0] * 3 for _ in range(2)]
    >>> A
    [[0, 0, 0], [0, 0, 0]]

    Not:
    >>> A = [0 * 3 for _ in range(2)]
    >>> A
    [0, 0]

  2. Essence of dfs: 1254. #Closed Islands

Via dfs template.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// not dfs template.
// nothing is done before/after dfs: Stack Overflow

public void fill(int[][] g, int i, int j) {
    if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] == 1) return;
    int m = g.length, n = g[0].length;
    for (i = 0; i < m; ++i) {
        for (j = 0; j < n; ++i) {
            for (int k = 0; k < 4; ++k) {
                fill(g, i + dir[k], j + dir[k+1]);
            }
        }
    }
}

1
2
3
4
5
6
7
// 2nd time FL: still wrnog: not reduce size of dfs
public void fill(int[][] g, int i, int j) {
    if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] == 1) return;
    for (int k = 0 ; k < dir.length-1; ++k) {
        fill(g, i + dir[k], j + dir[k+1]);
    }
}
1
2
3
4
5
6
7
8
// 3rd time FL: right
public void fill(int[][] g, int i, int j) {
    if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] == 1) return;
    g[i][j] = 1;
    for (int k = 0 ; k < dir.length-1; ++k) {
        fill(g, i + dir[k], j + dir[k+1]);
    }
}