@@ -0,0 +1,2112 @@
+package depth_first_search.matrix;%0A%0Apublic class Q1031NumberOfEnclaves %7B%0A%0A    //Difficulty: medium%0A    //TAG: dfs%0A    //TAG: bfs%0A%0A    /**%0A     * 1031. Number of Enclaves%0A     * Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)%0A     *%0A     * A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.%0A     *%0A     * Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.%0A     *%0A     *%0A     *%0A     * Example 1:%0A     *%0A     * Input: %5B%5B0,0,0,0%5D,%5B1,0,1,0%5D,%5B0,1,1,0%5D,%5B0,0,0,0%5D%5D%0A     * Output: 3%0A     * Explanation:%0A     * There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.%0A     * Example 2:%0A     *%0A     * Input: %5B%5B0,1,1,0%5D,%5B0,0,1,0%5D,%5B0,0,1,0%5D,%5B0,0,0,0%5D%5D%0A     * Output: 0%0A     * Explanation:%0A     * All 1s are either on the boundary or can reach the boundary.%0A     *%0A     *%0A     * Note:%0A     *%0A     * 1 %3C= A.length %3C= 500%0A     * 1 %3C= A%5Bi%5D.length %3C= 500%0A     * 0 %3C= A%5Bi%5D%5Bj%5D %3C= 1%0A     * All rows have the same size.%0A     */%0A%0A    /*%0A    Solution:%0A    eliminate all 1s that start from 1 on boundaries, then count rest of 1s%0A%0A    Time: O(mn)%0A    Space: O(max(m, n)) by dfs%0A     */%0A%0A    public int numEnclaves(int%5B%5D%5B%5D A) %7B%0A        if (A == null %7C%7C A%5B0%5D.length == 0) return 0;%0A        int row = A.length, col = A%5B0%5D.length;%0A        for (int i = 0; i %3C row; i++) %7B%0A            dfs(A, i, 0);%0A            dfs(A, i, col - 1);%0A        %7D%0A        for (int i = 0; i %3C col; i++) %7B%0A            dfs(A, 0, i);%0A            dfs(A, row - 1, i);%0A        %7D%0A        int count = 0;%0A        for (int%5B%5D arr: A) %7B%0A            for (int num: arr) %7B%0A                if (num == 1) count++;%0A            %7D%0A        %7D%0A        return count;%0A    %7D%0A%0A    private void dfs(int%5B%5D%5B%5D grid, int x, int y) %7B%0A        if (x %3C 0 %7C%7C x %3E= grid.length %7C%7C y %3C 0 %7C%7C y %3E= grid%5Bx%5D.length %7C%7C grid%5Bx%5D%5By%5D == 0) return;%0A        grid%5Bx%5D%5By%5D = 0;%0A        dfs(grid, x + 1, y);%0A        dfs(grid, x - 1, y);%0A        dfs(grid, x, y + 1);%0A        dfs(grid, x, y - 1);%0A    %7D%0A%0A%7D%0A

1031. Number of Enclaves