算法模板：BFS和DFS问题

BFS 常用于找单一的最短路线，它的特点是 "搜到就是最优解"
而 DFS 用于找所有解的问题，它的空间效率高，而且找到的不一定是最优解，必须记录并完成整个搜索，当然回溯不符合条件就会提前剪枝，这也是和普通的递归区别所在，需要满足边界条件以及判断条件两个，才能继续向下递归，不然直接返回上一步状态（回溯了），故一般情况下，深搜需要非常高效的剪枝（剪枝的概念请百度）。
DFS保证了避免“走老路”，返回标记位置的时候要将原场景恢复到第一次到达该节点的情况。

void dfs(int step)
{
        判断边界//判断是否符合条件
        {
            相应操作
        }
        枚举每一种可能
        {
               标记 //防止多次重复枚举同一个方案
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）//恢复现场
               //这就是DFS的精髓之处
               //为的就是不影响下一种方案的枚举
        }
}
    

const int N = 10;
int st[N]; 存储方案
bool book[N]; 标记数字是否被用过，true表示被用过，false表示没被用过
定义在里全局变量，所以现在book数组都是false 表示都没被用过
int n;
void dfs(int u){ 当前枚举第u位
    //每凑齐一个排列就输出
    if(u > n){
        for(int i = 1; i <= n; i ++) 
        printf("%d ", st[i]); 打印方案
        puts("");
        return ;
    }
    for(int i = 1; i <= n; i ++){ 依次枚举每个数
        if(!book[i]) 如果当前数没被用过
        {  //下面两行是递归前标记     
            st[u] = i;       在第u位是i
            book[i] = true;  标记用过
                
            dfs(u + 1);  递归到下一位

            //下面两行恢复现场，以便回溯其他情况
            st[u] = 0;  可省略 因为写不写都会被 st[u]=i; 这一层给覆盖掉
            book[i] = false;  不可省 
        }
    }
}
int main(){
    scanf("%d", &n);
    dfs(1);
    return 0;
}

int n,m;
int cnt[30]; 记录方案
void dfs(int u,int x){  u //记录枚举了几位也就是边界 x记录了枚举了到了几
	if(u>m) {  边界
		for(int i=1;i<=n;i++)
		cout<<cnt[i]<<" ";
		puts("");  换行
		return;
	}
	for(int i=x;i<=n;i++) 从x开始枚举
	{
        cnt[u]=i;
        dfs(u+1,i+1);//长度+1是肯定的，为什么是i+1呢？
        //原因是长度加1的时候，当然x作为当前数也一定要后移了，不然i不变岂不是被枚举的值一直不变，导致组合一直无法向后推进，长度增加值往后搜索，因为是求”组合“随机挑数，每一次（某一位置的枚举）的挑选方式都有O(n2)种，所以必须是for+dfs而不是  简单for
        cnt[u]=0; 恢复现场	
	}
}
int main()
{
	cin>>n>>m;
	dfs(1,1);
	return 0; 
}

package bfs;

import java.util.*;
//固定终点，改变矩阵看到达重点distance，如果修改为指定步数是否能达到，其实就是最后比较下大小，因为bfs解决了最短路径
public class Main {
    public static void main(String[] args) {
        int[][] tab = {
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 1, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0}
        };
        bfs(tab);
    }

    public static void bfs(int[][] tab) {
        //记录走到该坐标需要的最短步数 
        int[][] distance = new int[5][5];
        //记录移动的四个方位,在i循环中满足规则，比如i=0,代表x向右一个单位，因为一次只能移动一格，所以此时y必须对应为0，所以x和y中必有一个0；
        int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(0 ,0));
        while(!queue.isEmpty()) {
            Point p = queue.poll();
            //到达终点
            if(p.getX() == 4 && p.getY() == 4)
                break;
            //for中无敌递归，原因是bfs是依赖于队列的
            for(int i = 0; i < 4; i++) {
                //产生下一步坐标
                int x = p.getX() + dx[i];
                int y = p.getY() + dy[i];
                //越界判断，障碍判断，是否走过判断，必须得判断走过，如果BFS不进行标记的话，那就变成死循环了，会走以前的老路，但是为什么层序遍历不需要呢？
                //原因是层序遍历head会被pop，接着操作的只有left和right，所以不可能产生网上回去的情况
                if(x >= 0 && y >= 0 && x < 5 && y < 5 
                        && tab[x][y] != 1 && distance[x][y] == 0) {
                    queue.add(new Point(x, y));
                    //第一次经过的节点值一定是最小的，原因是上一步已经确定是最短的了，所以走这一步+1肯定也是最短的，就算queue中下一个节点也能扩展到这个节点
                    //但是它扩展也是需要1的步数，和第一次经过的节点步数是完全一样的，所以完全可以直接避免回头而一块判重，distance[x][y]保存第一次就好
                    //第一次经过一定是最短的，想想层序遍历，这里的每一个for只是一个节点的扩展，相当于一个node取left和right，层是没有明确划分的，一直判断满足不为空即可
                    // 每一层的节点距离一定是相等的，看谁先达到末尾。
                    //从一个角慢慢一层一层扩展到右下角，
                    distance[x][y] = distance[p.getX()][p.getY()] + 1;
                }
            }
        }
        System.out.println(distance[4][4]);
    }

}

//点类，用于存储坐标(x,y),不写成class的话，不能将其加入queue中
//写成map不行吗？map其实也行，只要能获取x，y即可，判重是通过distance是不是0判断的。
class Point {
    int x;
    int y;
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    public Point(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
}

void BFS ()
{
	 ① 初始化队列
	 ② 将起点入队
	 ③ 标记起点已经被访问
	 ④ while（ 队列不空时 ）
	 {
		 ⑤ 取出队首元素 u ，存放到 t 变量里 ，u 元素出队
		 ⑥ 扩展 t 结点
		 {
		 	⑦ 判重新节点
		 	⑧ 如果未被访问，且满足要求，记录当前点到起点的距离
		 	⑨ 标记扩展的新结点
		 	⑩ 将扩展的新节点入队
		 }
 	 }

}