岛屿问题——图DFS通用框架

public class Solution {
    /**
     * 判断岛屿数量
     * @param grid char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] grid) {
        //进行遍历
        int count = 0;
        for(int r = 0; r < grid.length; r++){
            for(int c = 0; c < grid[0].length; c++){

                if(grid[r][c] == '1'){
                    dfs(grid, r, c);
                    count++;
                }
            }
        }
        return count;
    }

    //图的通用dfs框架 相当于多叉树，但是我们要进行标记避免重复 
    public void dfs(char[][] grid, int r, int c){
        //判断base case
        //如果坐标(r,c)超过了网格范围，直接return
        if(!inArea(grid, r, c))
            return;
        //避免重复遍历
        if(grid[r][c] != '1')
            return;
        //进行标记
        grid[r][c] = '2';

        //访问上下左右
        dfs(grid, r-1, c);
        dfs(grid, r+1, c);
        dfs(grid, r, c-1);
        dfs(grid, r, c+1);
    }
    //不在岛屿内
    public boolean inArea(char[][] grid, int r, int c){
        return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
    }


}

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        for(int r = 0; r < grid.length; r++){
            for(int c = 0; c < grid[0].length; c++){
                if(grid[r][c] == 1){
                    res = Math.max(res, dfs(grid, r, c));
                }
            }
        }
        return res;
    }

    //遍历框架
    public int dfs(int[][] grid, int r, int c){

        //base case
        //判断有无越界
        if(!inArea(grid, r, c))
            return 0;
        if(grid[r][c] != 1)
            return 0;

        grid[r][c] = 2;
        return 1 + dfs(grid, r-1, c) + dfs(grid, r+1, c) + dfs(grid, r, c-1) + dfs(grid, r, c+1);
    }

    public boolean inArea(int[][] grid, int r, int c){
        return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;
    }
}

这时候也可以利用图的DFS框架来解决：
而我们的重点放在了周长上（格子的边）。很显然，题目只要与网格边界相邻的边和与海洋格子相邻的边。

class Solution {
    public int islandPerimeter(int[][] grid) {
        for(int r = 0; r < grid.length; r++){
            for(int c = 0; c < grid[0].length; c++){
                if(grid[r][c] == 1)
                    return dfs(grid, r, c);
            }
        }
        return 0;
    }

    public int dfs(int[][] grid, int r, int c){
        //base case 
        if(!inArea(grid, r, c))
            return 1;
        if(grid[r][c] == 0)
            return 1;
        if(grid[r][c] != 1)
            return 0;
        grid[r][c] = 2;
        return dfs(grid, r-1, c) + dfs(grid, r+1, c) + dfs(grid, r, c-1) + dfs(grid, r, c+1);
    }

    public boolean inArea(int[][] grid, int r, int c){
        return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
    }
}

类似岛屿问题的两道递归题

可以用图DFS的回溯框架，就是在每次递归完后，撤销对应的标记。

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        int[] flag = new int[matrix.length];
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(dfs(matrix, rows, cols, i, j, flag, 0, str)){
                    return true;
                }
            }
        }
        return false;
    }

    //其实参数是来控制递归的
    public boolean dfs(char[] matrix, int rows, int cols, int i, int j, int[] flag, int len, char[] str){
        int index = cols*i+j;    //计算当前点在matrix的位置
        if(i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[len] || flag[index] == 1)
            return false;    //超过格子 或者 不符合字符串 或者 走过
        if(len == str.length - 1)    //一旦满足字符串 
            return true;
        flag[index] = 1; //标记已走过
        //只需要一条路径即可
        if(dfs(matrix, rows, cols, i-1, j, flag, len+1, str) || dfs(matrix, rows, cols, i+1, j, flag, len+1, str)
          || dfs(matrix, rows, cols, i, j-1, flag, len+1, str) || dfs(matrix, rows, cols, i, j+1, flag, len+1, str))
            return true;
        //再撤销
        flag[index] = 0;
        return false;
    }

}

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        int[][] flag = new int[rows][cols];
        return helper(0, 0, rows, cols, flag, threshold);

    }

    public int helper(int i, int j, int rows, int cols, int[][] flag, int threshold){
        if(i < 0 || i >= rows || j < 0 || j >= cols || flag[i][j] == 1 || numSum(i) + numSum(j) > threshold){
            return 0;
        }
        flag[i][j] = 1;
        return helper(i+1, j, rows, cols, flag, threshold) + helper(i-1, j, rows, cols, flag, threshold)+
            helper(i, j+1, rows, cols, flag, threshold) + helper(i, j-1, rows, cols, flag, threshold) + 1;
    }

    public int numSum(int num){
        int sum = 0;
        while(num > 0){
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

其实还是DFS框架，只是在主程序直接返回DFS的结果。DFS的参数以及返回结果以及在主程序的逻辑都是根据题目来改变的，而核心的DFS框架不变。