DFS questions
unknown
java
a month ago
2.2 kB
75
Indexable
Never
// 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