DFS算法

DFS算法

DFS算法即：Depth First Search，深度优先搜索。这个算法的关键是解决“当下如何做”，至于下一步如何做和“当下如何做”是一样的，该算法从一个状态DFS(n)转移到下一个状态DFS（n+1），直到状态无法转移即到达临界点，然后回退到上一个状态，在上一个状态的基础上继续遍历其他状态，如此不断重复，直到找到最终解。如果算法有M个状态，每个状态有N种可能可以尝试，那么总的尝试次数是N^M 即M个N相乘。

算法的关注点：

1. 当下如何做，当下的状态如何处理
2. 如何转移到下一个状态，下一个状态有哪些可能？
3. 临界条件设定和dfs结束条件的设定以及处理
4. 标志位的设置和复位，标记资源被占用，以及当前使用后及时释放，留给下一次使用。

一般在进行DFS遍历的时候，会有一些限制条件，如已经用过的东西不能再使用，则需要对每次的使用做一个标记，然后转入到下一状态，并且从下一状态返回时候需要清除标记。

关键是分清状态和每种状态下的可能的区别。

全排列问题

如求数字1到N的全排列，准备N个盒子，每个盒子可以放入1~N中的任一数字，但是在放入数字的时候，不能放已经使用过的数字。当N个盒子放完后即完成一次全排列。
即有N种状态，每遍历一个盒子即为一个状态，遍历到最后一个盒子时候状态无法转移了，需要回退，然后在每个状态，又有N种可能可以尝试，即每个盒子可以放入1~N中的任一数字。

代码如下：

public class Test01 {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        dfsPermutation(0);
    }

    static int N = 6;//1~N的全排列
    static int[] box = new int[N];//用来放N个排列的数字
    static int[] book = new int[N+1];//对使用过的数字进行标记，数字即下标

    //对当下状态的处理，即N种可能尝试，每个盒子可以放入1~N中的任一数字
    //index 即数组box的下标，从0开始进行dfs遍历，直到N-1有效
    static void dfsPermutation(int index) {
        //达到临界条件，输出结果，中断遍历，返回上一状态
        if (index == N) {
            System.out.println(Arrays.toString(box));
            return;
        }
        
        //每个盒子可以放入1~N的数字，每个状态有N次尝试
        for (int i=1; i<=N; i++) {
            if (book[i] == 0) {//放入数字的时候有限制条件，只能使用未用过的数字i，未用过的数字的标记位 book[i]=0
                box[index] = i; //把数字 i 放入到box数组，生成全排列
                book[i] = 1;//标记数字i 已经被使用了
                dfsPermutation(index+1); //进入到下一次转移
                
                book[i] = 0;//从上一个状态返回时，清空i的使用标志，进行下一个尝试
            }
        }
    }   
}

迷宫问题

定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左
上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。
Input
一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

编程实现：

public class Test01 {
    static int[][] maze1 = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 1, 0}};
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);        
            int[][] book = new int[6][6];
            dfs(maze1, book, 0, 0, 1);
            printPoints(points);
            
    }
    

    static int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};//4个方向

    static int[][] points;
    // steps 第几个状态 从1开始
    static void dfs(int[][] map, int[][] book, int x, int y, int steps) {
        
        //到终点的处理
        if (x == map.length-1 && y == map[0].length-1) {
            
            book[x][y] = steps; //保存状态序号
 
            int[][] ps = new int[steps][2];
            //获取路径坐标
            for (int i=0; i<book.length; i++) {
                for (int j=0; j<book[0].length; j++) {
                    if (book[i][j] != 0) {
                        ps[book[i][j]-1][0] = i;//根据状态序号决定顺序
                        ps[book[i][j]-1][1] = j;
                    }
                }
            }
            points = ps;

            book[x][y] = 0;
            return;
        }
        
        //当下状态的处理
        
        for (int i=0; i<4; i++) {//该状态下尝试4个方向
            book[x][y] = steps;//保存状态序号

            int toX = x+next[i][0];
            int toY = y+next[i][1];
            //边界判断，路径判断
            if (toX >= 0 && toX < map.length && toY >= 0 && toY < map[0].length) {
                if (map[toX][toY] == 0 && book[toX][toY] == 0) {
                    dfs(map, book, toX, toY, steps+1);
                }
            }

            book[x][y] = 0;//清除标记
        }
       
    }
 
    static void printPoints(int[][] a) {
        if (a == null) return;
        for (int i=0; i<a.length; i++) {
            System.out.printf("(%d,%d)\n",a[i][0],a[i][1]);
        }
    }

}

矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

其实就是dfs算法，类似找迷宫。

public class Solution {
    static public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
     {
         if (matrix == null || str == null || str.length == 0 || 
             matrix.length == 0 || matrix.length != rows*cols) return false;
             
         for (int i=0; i<rows; i++) {
             for (int j=0; j<cols; j++) {
                 //寻找起始位置
                 if (matrix[i*cols+j] == str[0]) {
                     isHas = false;
                     dfs(matrix, rows, cols, new int[rows*cols], str, 0, j, i);
                     if (isHas) 
                         return isHas;
                 }
             }
         }
         
         return false;
     }
     
     static boolean isHas = false; //找到字符串标志
     //book是用来标记一个位置是否被进入过
     //id 是遍历str字符串时的下标
     //x,y是对应二维矩阵中的坐标位置
     static void dfs(char[] matrix, int rows, int cols, 
                     int[] book, char[] str, int id, int x, int y) {
         //字符串被找到
         if (id == str.length) {
             isHas = true;
             return ;
         }
         
         //边界判断
         if (x < 0 || x >= cols || y < 0 || y >= rows) return;
         
         int index = x + y*cols;//对应matrix下标
         if (matrix[index] == str[id] && book[index] == 0) {
             book[index] = 1;//标志已经进入
             //进入下一批格子
             int[][] next = {{0,1},{1,0},{0,-1},{-1,0}};
             for (int i=0; i<4; i++) {
                 int tx = x + next[i][0];
                 int ty = y + next[i][1];
                 dfs(matrix, rows, cols, book, str, id+1, tx, ty);
             }
             
             book[index] = 0;//清除标志
         }
     }

}