DFS算法
DFS算法即：Depth First Search，深度优先搜索。这个算法的关键是解决“当下如何做”，至于下一步如何做和“当下如何做”是一样的，该算法从一个状态DFS(n)转移到下一个状态DFS（n+1），直到状态无法转移即到达临界点，然后回退到上一个状态，在上一个状态的基础上继续遍历其他状态，如此不断重复，直到找到最终解。如果算法有M个状态，每个状态有N种可能可以尝试，那么总的尝试次数是N^M 即M个N相乘。
算法的关注点：
- 当下如何做，当下的状态如何处理
- 如何转移到下一个状态，下一个状态有哪些可能？
- 临界条件设定和dfs结束条件的设定以及处理
- 标志位的设置和复位，标记资源被占用，以及当前使用后及时释放，留给下一次使用。
一般在进行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;//清除标志
}
}
}
