DFS questions

mail@pastecode.io avatar
unknown
java
5 months ago
2.2 kB
80
Indexable
// leetcode 695 ====================================

class Solution {
    public int findArea(int row, int col, int[][] grid){
        grid[row][col] = 0;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};

        int currArea = 1;

        for(int [] dir : dirs){
            int nRow = row + dir[0];
            int nCol = col + dir[1];

            if(nRow < grid.length && nCol < grid[0].length && nRow >= 0 && nCol >= 0 && grid[nRow][nCol] == 1){
                currArea += findArea(nRow, nCol, grid);
            }
        }
        return currArea;
    }

    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;

        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] == 1){
                    int currArea = findArea(i,j,grid); // find current island area, convert 1s to 0s

                    maxArea = Math.max(maxArea, currArea);
                }
            }
        }

        return maxArea;
    }
}


// leetcode 130 ===================================

class Solution {
    public void changeOtoHash(int row, int col, int n, int m, char[][] board){
        board[row][col] = '#';

        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};

        for(int [] dir: dirs){
            int nRow = row + dir[0];
            int nCol = col + dir[1];

            if(nRow < n && nCol < m && nRow >= 0 && nCol >= 0 && board[nRow][nCol] == 'O'){
                changeOtoHash(nRow,nCol,n,m,board);
            }
        }
    }

    public void solve(char[][] board) {
        int n = board.length;
        int m = board[0].length;

        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++){
                if(i==0 || j==0 || i==n-1 || j==m-1){
                    if(board[i][j] == 'O'){
                        changeOtoHash(i,j,n,m,board);
                    }
                }
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j] == '#'){
                    board[i][j] = 'O';
                } else if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }
}

// leetcode 1020, 463, 1905
Leave a Comment