Common Java DFS


  • 0
    T
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int y = 0; y < grid.length; y++) {
            for (int x = 0; x < grid[0].length; x++) {
                if (grid[y][x] == '1') {
                    dfs(grid, y, x);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void dfs(char[][] grid, int y, int x) {
        grid[y][x] = '0';
        Stack<Integer> yPos = new Stack<Integer>();
        Stack<Integer> xPos = new Stack<Integer>();
        yPos.push(y);
        xPos.push(x);
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!yPos.isEmpty()) {
            y = yPos.pop();
            x = xPos.pop();
            for (int[] d : dirs) {
                int dy = y + d[0];
                int dx = x + d[1];
                if (dy >= 0 && dy < grid.length && dx >= 0 && dx < grid[0].length && grid[dy][dx] == '1') {
                    grid[dy][dx] = '0';
                    yPos.push(dy);
                    xPos.push(dx);
                }
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.