岛屿问题(dfs)

leetcode 200 岛屿数量 class Solution { public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1'){ dfs(grid,i,j); count++; } } } return count; } private void dfs(char[][] grid, int i, int j) { if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){ return; } grid[i][j] = '0'; dfs(grid,i+1,j); dfs(grid,i,j+1); dfs(grid,i-1,j); dfs(grid,i,j-1); } } leetcode 695 岛屿的最大数量 class Solution { public int maxAreaOfIsland(int[][] grid) { if (grid == null) { return 0; } int res = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { int area = dfs(grid, i, j); res = Math.max(area, res); } } return res; } private int dfs(int[][] grid, int i, int j) { if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0) { return 0; } grid[i][j] = 0; return 1 + dfs(grid, i + 1, j) + dfs(grid, i, j + 1) + + dfs(grid, i - 1, j) + + dfs(grid, i, j - 1); } } leetcode 463 岛屿的周长 class Solution { public int islandPerimeter(int[][] grid) { if (grid == null) { return 0; } for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { return dfs(grid, i, j); } } } return 0; } private int dfs(int[][] grid, int i, int j) { if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) { return 1; } if (grid[i][j] == 0) { return 1;// 对应海洋 } if (grid[i][j] != 1) {// 当前是已经遍历过的陆地格子 return 0; } grid[i][j] = 2; return dfs(grid, i + 1, j) + dfs(grid, i, j + 1) + dfs(grid, i - 1, j) + dfs(grid, i, j - 1); } }