相关文章：

数据结构与算法 — 运用DFS算法处理组合类和摆放类问题（一维）

在上一篇文章中，咱们介绍了经过DFS算法解决组合类以及摆放类的问题，主要用于解决一维数组的问题，例如字符串数组、int数组的摆放组合问题，那么假如数据集是二维数组，例如矩阵，通常会用来解决途径问题，那么怎么经过DFS算法解决此类问题，接下来会具体介绍。

1 矩阵基础知识

1.1 矩阵的遍历

矩阵通常为一个n*m的数组结构，咱们能够理解为是多维的数组，首先咱们先需求知道，怎么遍历矩阵。

public static int[][] matrix = {{2, 3, 5}, {4, 7, 9}};
public static void matrixForeach() {
    for (int i = 0; i < matrix.length; i  ) {
        for (int j = 0; j < matrix[i].length; j  ) {
            Log.d(TAG, "matrixForeach: i = "   i   "j = "   j   " "   matrix[i][j]);
        }
    }
}

假如学习过线性代数，咱们知道行列式和矩阵的区别在于，行列式是n行n列，但是矩阵没有这个约束，所以在遍历的时分，咱们能够先拿到有多少行，即matrix的长度；拿到某一行的数组之后，这一行的数组元素个数就是列数。

matrixForeach: i = 0 j = 0 2
matrixForeach: i = 0 j = 1 3
matrixForeach: i = 0 j = 2 5
matrixForeach: i = 1 j = 0 4
matrixForeach: i = 1 j = 1 7
matrixForeach: i = 1 j = 2 9

1.2 矩阵内部的移动

回到问题的本身，假如咱们想要做二维数组内部的DFS途径问题，假如有必要得知道怎么在矩阵内部做移动，如下图所示：

元素2能够上下左右移动（理论上），但图中2仅能够向右或许向下移动，因而2会有两条路线，假如选择向右到达下一个点之后，仍然采纳相同的策略，终究会拿到一条线路；此刻回溯到2能够选择向下持续寻觅途径。

从上图中咱们能够看到，元素2的位置为(0,0)，其左侧的元素(0,-1)，右侧的元素为(0,1)，上方的元素为(-1,0)，下方的元素为(1,0)，所以左右方向的查找是列数的改动，上下方向的查找是行数的改动。

//0 上 1 下 2 左 3 右
private static int dx(int orientation) {
    if (orientation == 0) {
        return -1;
    } else if (orientation == 1) {
        return 1;
    }
    return 0;
}
private static int dy(int orientation) {
    if (orientation == 2) {
        return -1;
    } else if (orientation == 3) {
        return 1;
    }
    return 0;
}

所以二维数组的查询跟一维数组的不同之处在于，二维的需求上下左右的找，而一维数组只需求从左向右找即可，也就是说控制startIndex的方式不一样，但递归回溯的思维不变。

由于矩阵中每一个元素都能够作为起点，所以需求遍历整个数组元素，对每一个元素执行上下左右的深度优先查找。

public static void findPath() {
    boolean[][] visited = new boolean[matrix.length][matrix[0].length];
    List<String> result = new ArrayList<>();
    for (int i = 0; i < matrix.length; i  ) {
        for (int j = 0; j < matrix[i].length; j  ) {
            visited[i][j] = true;
            move(matrix, i, j, visited,matrix[i][j] "", result);
            visited[i][j] = false;
        }
    }
    Log.d(TAG, "matrixForeach: result"   result);
}
/**
 * 二维数组途径查找
 *
 * @param nums    二维数组
 * @param x       行数
 * @param y       列数
 * @param visited 当时节点是否被拜访过了
 */
public static void move(int[][] nums,
                        int x,
                        int y,
                        boolean[][] visited,
                        String subset,
                        List<String> result) {
    //出口
    Log.d(TAG, "move: "   subset);
    //什么样的规范能够找到悉数途径呢
    //上下左右找
    for (int i = 0; i < 4; i  ) {
        int dx = x   dx(i);
        int dy = y   dy(i);
        //假如没有在界内 或许现已被拜访过了，就不管
        if (!isInside(nums, dx, dy) || visited[dx][dy]) {
            continue;
        }
        visited[dx][dy] = true;
        move(nums, dx, dy, visited, subset   nums[dx][dy], result);
        visited[dx][dy] = false;
    }
}

当然在上下左右遍历元素的时分，假如呈现数组越界或许现已拜访了这个元素，那么就不需求走这个方向了，换其他的方向持续查找即可。

//判别是否越界
private static boolean isInside(int[][] nums, int x, int y) {
    return (x >= 0 && x < nums.length) && (y >= 0 && y < nums[x].length);
}

2 途径问题 – 无固定起点

那么在了解了矩阵的基础知识之后，咱们能够运用深度优先搜素途径这个模板，解决一系列的途径问题。

2.1 单词查找

给定一个m x n二维字符网格board和一个字符串单词word。假如word存在于网格中，返回true；否则，返回false。

单词有必要依照字母顺序，经过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或笔直相邻的单元格。同一个单元格内的字母不允许被重复运用。

示例 1：

输入： board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出： true

示例 2：

输入： board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出： true

这道题是要咱们查找二维矩阵中是否经过某个途径构成一个单词，这道题其实就是经典的途径问题，咱们能够经过查找悉数的途径，来匹配要查询的单词，模板仍然是1.2末节中。

public boolean exist(char[][] board, String word) {
    if(board == null || board.length == 0){
        return false;
    }
    boolean[][] visited = new boolean[board.length][board[0].length];
    //构建前缀调集
    List<String> prefix = new ArrayList();
    for(int i = 1;i<=word.length();i  ){
        prefix.add(word.substring(0,i));
    }
    List<String> results = new ArrayList();
    //遍历矩阵
    for(int i = 0;i < board.length;i  ){
        for(int j = 0;j < board[i].length;j  ){
            visited[i][j] = true;
            dfs(board,i,j,visited,board[i][j] "",results,word,prefix);
            visited[i][j] = false;
        }
    }
    return results.size() > 0;
}
private void dfs(char[][] board,
                 int x,
                 int y,
                 boolean[][] visited,
                 String subset,
                 List<String> results,
                 String word,
                 List<String> prefix){
    //假如前缀不一致，直接return
    if(!prefix.contains(subset)){
        return;
    }
    if(subset.equals(word)){
        results.add(subset);
    }
    for(int i = 0;i<4;i  ){
        int dx = x   dx(i);
        int dy = y   dy(i);
        //假如越界 或许 拜访过元素，越过即可
        if(!inside(board,dx,dy) || visited[dx][dy]){
            continue;
        }
        visited[dx][dy] = true;
        dfs(board,dx,dy,visited,subset board[dx][dy],results,word,prefix);
        visited[dx][dy] = false;
    }
}
//基础办法
// 0 上 1 下 移动
private int dx(int orientation){
    if(orientation == 0){
        return -1;
    }else if(orientation == 1){
        return 1;
    }
    return 0;
}
// 2 左 3 右 移动
private int dy(int orientation){
    if(orientation == 2){
        return -1;
    }else if(orientation == 3){
        return 1;
    }
    return 0;
}
//判别是否越界
public boolean inside(char[][] arr,int x,int y){
    return (x >= 0 && x < arr.length) && (y >= 0 && y < nums[x].length);
}

这儿咱们先构建了查找单词的前缀数组，假如途径与前缀不匹配，那么就中止查找；假如匹配到了单词，那么就存到一个数组中，终究判别数组是否为空。

当然这个算法存在优化的空间，由于咱们找到单词之后后续的途径能够中止寻觅。

3 途径问题 – 有固定起点

3.1 LeetCode64 – 最小途径和问题

给定一个包括非负整数的mxn网格grid，请找出一条从左上角到右下角的途径，使得途径上的数字总和为最小。

阐明： 每次只能向下或许向右移动一步。

示例 1：

输入： grid = [[1,3,1],[1,5,1],[4,2,1]]
输出： 7
解说： 由于途径 1→3→1→1→1 的总和最小。

像这道题，由于题目要求是要从左上角动身，终点是左下角；并且只能向下或许向右移动，只要2个方向，那么就能够归结为经典的二叉树问题，选用二叉树的深度优先算法，如下图。

这儿需求留意一点，就是当一向往下的时分，例如（2，0）的位置，此刻在递归的出口处无法阻拦，此刻会持续进入到dfs中，此刻需求做鸿沟的判别，假如超出行、或许列数时，和不变即可，尔后进入到出口时会被return，回溯转向右侧分支，此刻右侧分支的行数一定不会越界，只需求关注列数的鸿沟即可。

public int minPathSum(int[][] grid) {
    if(grid == null || grid.length == 0){
        return 0;
    }
    int[] min = {Integer.MAX_VALUE};
    dfs(grid,0,0,grid[0][0],min);
    return min[0];
}
private void dfs(int[][] grid,
                 int x,
                 int y,
                 int sum,
                 int[] min){
    if (x < 0 || y < 0 || x >= grid.length || y >= grid[x].length) {
        return;
    }
    if (x == grid.length - 1 && y == grid[x].length - 1) {
        //到了右下角了
        min[0] = Math.min(min[0], sum);
        return;
    }
    //只能移动两个方向
    for (int i = 0; i < 2; i  ) {
        int dx = x   dx3(i);
        int dy = y   dy3(i);
        dfs(grid, dx, dy, sum   ((dx == grid.length || dy == grid[dx].length) ? 0 : grid[dx][dy]), min);
    }
}
// 0 下 1 右
// 当向下走时，x   1，y 不变
// 当向右走时，x 不变， y   1
private static int dx3(int orientation) {
    if (orientation == 0) {
        // 下
        return 1;
    } else {
        // 右
        return 0;
    }
}
private static int dy3(int orientation) {
    if (orientation == 0) {
        return 0;
    } else {
        return 1;
    }
}

3.2 LeetCode120 – 三角形最小途径和

给定一个三角形triangle，找出自顶向下的最小途径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这儿指的是下标与上一层结点下标相同或许等于上一层结点下标 1的两个结点。也就是说，假如正坐落当时行的下标i，那么下一步能够移动到下一行的下标i或i 1。

示例 1：

输入： triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出： 11
解说： 如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小途径和为11（即，2 3 5 1= 11）。

相同，这道题咱们也要求咱们从原点动身，并且只能走到相邻节点上，如下图所示：

像这种规范的平衡二叉树，关于鸿沟问题的处理，只需求判别当时x，也就是行数是否超过二维数组的行数作为出口即可。

public int minimumTotal(List<List<Integer>> triangle) {
    if(triangle == null || triangle.size() == 0){
        return 0;
    }
    int[] min = {Integer.MAX_VALUE};
    dfs(triangle,0,0,triangle.get(0).get(0),min);
    return min[0];
}
private void dfs(List<List<Integer>> triangle,
                 int x,
                 int y,
                 int sum,
                 int[] min){
    if (x == triangle.size() - 1) {
        min[0] = Math.min(min[0], sum);
        return;
    }
    if (!inside(triangle,x,y)){
        return;
    }
    //只要两步路能够走
    dfs(triangle,x 1,y,sum triangle.get(x 1).get(y),min);
    dfs(triangle,x 1,y 1,sum triangle.get(x 1).get(y 1),min);
}