BFS

BFS是一个先入先出的过程，所以用队列来存储有效状态。

步骤

1. 创建队列，以便后续将有效状态放入其中
2. 创建标记访问visit数组，用来标记这一状态是否已经访问过，但是有的时候需要用到map，因为访问对象有可能不是int类型。例题：https://www.nowcoder.com/practice/761fc1e2f03742c2aa929c19ba96dbb0?tpId=60&tqId=29484&tPage=1&ru=%2Fkaoyan%2Fretest%2F1001&qru=%2Fta%2Ftsing-kaoyan%2Fquestion-ranking&tab=answerKey
3. 有时需要自己定义结构体来存放状态Status
4. 循环模版：

struct Status{
    string str;  // 字符串
    int cnt; // 已经移动的次数
    Status(string str, int cnt):str(str),cnt(cnt){}
};

queue<Status> q;
q.push(Status(str, 0));  // 初始状态
while(!q.empty()){
    Status cur = q.front();
    q.pop();
    // 已经找到
    if(满足条件)
        return 当前查找步数或者其他
    for(遍历所有的搜索){
            Status next = ...   // 下一个有效状态
            if(visit)     // 如果已经访问过，就跳过这次循环
                          // 应该为一个visit数组，这里简单用visit代替
                continue;
            q.push(next);
            visit = true;
    }
}

DFS

获得一个状态后，立即扩展这个状态，但需要保证先得到的状态较后扩展，所以用栈或者递归来处理。由于不是先入先出，所以往往搜索到的状态不具有最优的特性。

经典例题：迷宫求解

• 题目大意：给定起点，终点，以及棋盘中的障碍物位置，一共有上下左右四个移动位置，求从起点到终点共有几条路。
• 题解：可以设置一个全局变量num，每次找到一个解，num++，最终输出num即可。
• 我犯过的错误：将DFS(int x, int y, int step)作为搜索函数，每次找到之后返回step，递归的时候用语句return DFS(x,y,step+1)。这样做为什么不对我现在也没有很想明白，毕竟我也觉得这样没有什么道理，还是跟着正确的思路做，一步步学吧。应该直接DFS，而不是return
• 记得起点visit设置为true，DFS之后要回溯，把之前设置为true的，现在设为false
• 代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int grid[10][10];
int n,m;
int sx, sy, fx, fy;  // 终点和起点
bool visit[10][10];  // 标记是否访问
int t;  // 障碍个数
int direction[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; // 四个方向
int block[10][10];  // 标记迷宫障碍
int num = 0;

// 看该点能否访问
bool Judge(int x, int y){
    if(visit[x][y] == true || x<=0 || y <=0 || x >n || y > m)
        return false;
    return true;
}

void DFS(int x, int y){
    if(x == fx && y == fy)
        num++;
    for(int i = 0; i < 4; i++){
        int nx = x+direction[i][0];  // 新扩充的x坐标
        int ny = y+direction[i][1];  // 新扩充的y坐标
        if(!Judge(nx, ny))
            continue;
        visit[nx][ny] = true;
        DFS(nx, ny);
        visit[nx][ny] = false;
    }
}

int main(){
    memset(block, 0, sizeof(block));
    cin>>n>>m>>t;  // 板面大小 障碍个数
    cin>>sx>>sy>>fx>>fy;  // 起点与终点
    visit[sx][sy] = true;  // 标记起点
    while(t--){
        int temp1,temp2;
        cin>>temp1>>temp2;
        visit[temp1][temp2] = 1;  // 把有障碍的地方标记为true
    }
    DFS(sx,sy);
    cout<<num<<endl;
}

DFS与BFS

因此DFS为了知道问题是否有解，或者求解的个数，而BFS用来求最优解。

• DFS：获得一个状态以后立即用递归扩展。所以如果扩展失败，如果有visit数组，需要将visit数组的值置为false
• BFS：将当前状态全部扩展完再扩展新的状态。一般用队列存储扩展的状态，当q非空的时候循环。

DFS模版

res = [] 每次路径搜索完成后的结果集 
path = [] 搜索的路径

def backtrack(未探索区域, res, path):
    if path 满足条件:
        res.add(path) # 深度拷贝
        # return  # 如果不用继续搜索需要 return
    for 选择 in 未探索区域当前可能的选择:
        if 当前选择符合要求:
            path.add(当前选择)
            backtrack(新的未探索区域, res, path)
            path.pop()

参考链接

DFS练习题

子序列求和等于定值

leetcode39
leetcode40

• 这两个题的不同之处在于，39题同一个元素可以使用多次，这样的话DFS中参数是从i开始的，而40题同一个元素只能使用一次，DFS中参数从i+1开始。另外，DFS函数中的startIndex 参数很重要，否则会出现很多实际上重复的元素，比如{1,2,5}, {2,1,5}，当然也可以用map来去重，但是会增加复杂度，最好在一开始就不去遍历。
• 经典判断条件，这个循环条件一定要把i>=1放在前面，否则有的OJ会出现越界的情况。

if(visit[i] || (i >=1 &&candidates[i] == candidates[i-1] && !visit[i-1]))

• 注意剪枝

for(int i = start; i < candidates.size() && cur_sum+candidates[i] <= target; i++)