搜索 专题

DFS 模板

模板

int DFS(int t)
{
    if(满足输出条件)
    {
        输出解;
        return;
    }
    else
    {
        for(int i = 1;i <= 尝试方法数; ++i)
            if(满足进一步搜索条件)
            {
                为进一步搜索所需要的状态打上标记;
                DFS(t+1);
                恢复到打标记前的状态;  //回溯
            }
    }
}

注意点

1.第一个 if 是符合输出解的条件，第二个 if 是符合进一步搜索的条件；

2.下一步搜索时，不是使用 return DFS(t+1)，而是直接 DFS(t+1);

3.for 循环之后的 if 可以是多个;

4.for 循环边界，例如：

  • 方向是四个，那么边界肯定就是 4；

  • 素数环需要尝试 1 至 20，那么边界就是 20；