参考课程是我高中信息竞赛邱老师的课程。
【14-2 搜索：深度优先搜索1(图的遍历)】 https://www.bilibili.com/video/BV1JZ421a7oR/?share_source=copy_web&vd_source=2c56c6a2645587b49d62e5b12b253dca
【14-3 搜索：深度优先搜索2】 https://www.bilibili.com/video/BV1Ex4y1k7Kz/?share_source=copy_web&vd_source=2c56c6a2645587b49d62e5b12b253dca
【14-2、3 深度优先搜索习题解答】 https://www.bilibili.com/video/BV1jJ4m1Y7LA/?share_source=copy_web&vd_source=2c56c6a2645587b49d62e5b12b253dca
完整的ACM/CSP板子可以去我资源中领，我设的0积分应该是免费的，如果要花钱B站私我。
DFS
DFS的链式前向星实现
DFS的二维vector实现
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> graph(1000005);
bool vis[1000005];
int N,M,u,v;
void dfs(int i){
cout<<i<<" ";
for(int j = graph[i].size() – 1; j >= 0; j–){//遍历他前驱节点
if(!vis[graph[i][j]]){
vis[graph[i][j]]=true;
dfs(graph[i][j]);
}
}
}
int main(){
cin>>N>>M;
for(int i=0;i<M;i++){
cin>>u>>v;
graph[u].push_back(v);
}
for(int i=1;i<=N;i++){
if(!vis[i]){
vis[i]=true;
dfs(i);
}
}
cout<<endl;
return 0;
}
最长路问题——带回溯的DFS
T429775
https://www.luogu.com.cn/problem/T429775
#include<bits/stdc++.h>
using namespace std;
int N,M,u,v;
struct Edge{
int v,next;
};
Edge E[20005];
int fst[1005];
int L=1;
bool vis[1005];
int cnt;//记录路长
int ans;
void addEdge(int u,int v){
E[L].v=v;
E[L].next=fst[u];
fst[u]=L++;
}
void dfs(int i){
ans=max(ans,cnt);
for(int p=fst[i];p;p=E[p].next){
int v=E[p].v;
if(!vis[v]){
vis[v]=true;
cnt++;
dfs(v);
vis[v]=false;
cnt–;
}
}
}
int main(){
cin>>N>>M;
for(int i=0;i<M;i++){
cin>>u>>v;
addEdge(u,v);
}
vis[1]=true; cnt++;
dfs(1);
cout<<ans;
}
统一模板
一定要明确搜索方式，是按行搜索？按个搜索？按节点搜索？
在这种搜索方式下，每个搜索节点会面临什么状态(选or不选（复习背包/取数游戏）？这一行的所有列（皇后）)》？
dfs一开始就要考虑终止条件、切换遍历顺序条件（换行）
注意：如果涉及多次查询，记得memset图和vis数组。
如果是一次多个选项可以引入初始节点
确定是否需要回溯，如果要找多种可能，就一定要回溯。
确认是否需要vis，如果不允许两次选择同一个状态就vis
可以提前确认有哪些状态，for的时候就找这几种状态，然后if判断是否可以转移
按什么规律去找（按行？按层？） 这个规律下每次会遇到哪些状态？ 如何判断哪些状态可行？
例题
P1706
https://www.luogu.com.cn/problem/P1706
#include<iostream>
using namespace std;
bool vis[1005];
int n,cnt;
int ans[10];
void ptnans(){
for(int i=0;i<n;i++){
cout<<" "<<ans[i];
}
cout<<endl;
}
void dfs(int i){
if(cnt==n){
ptnans();
}
for(int j=1;j<=n;j++){
if(!vis[j]){
vis[j]=true;
ans[cnt++]=j;
dfs(j);
vis[j]=false;
cnt–;
}
}
}
int main(){
cin>>n;
dfs(0);
}
二维地图DFS
https://www.luogu.com.cn/problem/P1605
P1605
#include<bits/stdc++.h>
using namespace std;
int maze[10][10];
bool vis[10][10];
int N,M,T,cnt,FX,FY;
int curx,cury;
int f[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int curx,int cury){
if(curx==FX && cury==FY){
cnt++;
return;
}
for(int i=0;i<4;i++){
//去看看当前四周
int nextx=curx+f[i][0],nexty=cury+f[i][1];
if(nextx<=N&&nextx>0 && nexty<=M&&nexty>0 && maze[nextx][nexty]!=-1&&!vis[nextx][nexty]){
vis[nextx][nexty]=true;
dfs(nextx,nexty);
vis[nextx][nexty]=false;
}
}
}
int main(){
cin>>N>>M>>T;
cin>>curx>>cury>>FX>>FY;
for(int i=0;i<T;i++){
int obsx,obsy;
cin>>obsx>>obsy;
maze[obsx][obsy]=-1;
}
vis[curx][cury]=true;
dfs(curx,cury);
cout<<cnt<<endl;
}
对角线规则
对角线的值和是定值；反对角线的行列差是定值（由于存在负数必须偏移）。
皇后问题 P1219
https://www.luogu.com.cn/problem/P1219
按什么规律去找（按行？按层？） 这个规律下每次会遇到哪些状态？ 如何判断哪些状态可行？
按行遍历，每一列都是状态，需要判断是否在此前任意节点的对角线、反对角线、列上。 如何存储这些：用vis数组，第一行存列占用，第二行存对角线占用，第三行存储反对角线占用。
if(!vis[0][j]&&!vis[1][i+j]&&!vis[2][i-j+20])
#include<bits/stdc++.h>
using namespace std;
int vis[3][50];
int ans[15];
int n,cnt,ansnum;
void dfs(int i){
if(i==n){
ansnum++;
if(ansnum<=3){//输出ans
for(int i=0;i<n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
for(int j=1;j<=n;j++){
//用vis数组，第一行存列占用，第二行存对角线占用，第三行存储反对角线占用
if(!vis[0][j]&&!vis[1][i+j]&&!vis[2][i-j+20]){
vis[0][j]=vis[1][i+j]=vis[2][i-j+20]=true;
ans[cnt++]=j;
dfs(i+1);
vis[0][j]=vis[1][i+j]=vis[2][i-j+20]=false;
cnt–;
}
}
}
int main(){
cin>>n;
dfs(0);
cout<<ansnum<<endl;
}
复习背包/DFS P2392
https://www.luogu.com.cn/problem/P2392
很诡异的解法，
按什么规律去找（按行？按层？） 这个规律下每次会遇到哪些状态？ 如何判断哪些状态可行？
按题目去找到，每道题目两种情况，一种是选，一种不选，选不选都会进入dfs(k,i+1)状态 都是可以的，不需要判断可行性。
#include<bits/stdc++.h>
using namespace std;
int s[4];//科目题目数量
int t[4][100];
int ans[4],cur[4],half[4];
void dfs(int k,int i){//第k门 第i题
if(cur[k]>=half[k]){//如果超过一半时间就停止，然后对比
ans[k]=min(ans[k],cur[k]);
return;
}
if(i==s[k]) return ;//或者直接达到最后一道题
//否则就尝试把这道题加入cur
cur[k]+=t[k][i];
dfs(k,i+1);
cur[k]-=t[k][i];//另一种情况是把i题放到另一侧，然后继续dfs
dfs(k,i+1);
}
int res=0;
int main(){
cin>>s[0]>>s[1]>>s[2]>>s[3];
for(int i=0;i<4;i++){
for(int j=0;j<s[i];j++){
cin>>t[i][j];
ans[i]+=t[i][j];
}
half[i]=(ans[i]+1)/2;
dfs(i,0);
res+=ans[i];
}
cout<<res<<endl;
}
细胞数量 P1451
遇到需要扩展一片的题，先考虑DFS，对图的所有位置进行一次DFS
https://www.luogu.com.cn/problem/P1451
这道题告诉我们，不一定是所有DFS都需要内部判断的，有时候只需要打标记即可
//通过DFS搜索一片的细胞 给这一片都打上vis
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int maze[105][105];
int vis[105][105];
int f[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int curx,cury,nextx,nexty;
void dfs(int curx,int cury){
for(int i=0;i<4;i++){
nextx=curx+f[i][0];nexty=cury+f[i][1];
if(nextx&&nexty&&nextx<=n&&nexty<=m&&!vis[nextx][nexty]&&maze[nextx][nexty]!=0){
vis[nextx][nexty]=true;
dfs(nextx,nexty);
}
}
}
int main(){
cin>>n>>m;
char temp;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>temp;
maze[i][j]=temp-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!vis[i][j]&&maze[i][j]){
cnt++;
vis[i][j]=true;
dfs(i,j);
}
}
}
cout<<cnt<<endl;
}
vis的双重锁问题 取数游戏 P1123
https://www.luogu.com.cn/problem/P1123
这道题的难点在于不是相邻扩展的，而是只能向右下拓展的，这类题目最难就在于找到拓展方式，判定函数都好写。
下面的代码是WA的，因为vis被设为了bool，只有01状态。但是有可能ABA这种情况，B被锁了两次，此时撤回A就不可以直接设B=false了。这时就需要引入数值锁。
//这道题的难点在于不是相邻扩展的，而是只能向右下拓展的，这类题目最难就在于找到拓展方式，判定函数都好写。
//第二个坑：由于可能vis重合，有双重锁，不能一次就改为false。
#include<bits/stdc++.h>
using namespace std;
int vis[7][7];
int maze[7][7];
int T;
int N,M;
int sum,ans;
int f[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
void save(int i,int j){//把当前周伟8格vis
for(int k=0;k<8;k++){
int nx = i + f[k][0];
int ny = j + f[k][1];
if(nx >= 1 && nx <= N && ny >= 1 && ny <= M) {
//vis[nx][ny]==true;
vis[nx][ny]++;
}
}
sum+=maze[i][j];
}
void restore(int i,int j){//把当前周伟8格vis
for(int k=0;k<8;k++){
int nx = i + f[k][0];
int ny = j + f[k][1];
if(nx >= 1 && nx <= N && ny >= 1 && ny <= M) {
//vis[nx][ny]=false;
vis[nx][ny]–;
}
}
sum-=maze[i][j];
}
void dfs(int i,int j){
if(i==N+1){
ans=max(ans,sum);
return;
}
if(j==M+1){
dfs(i+1,1);
return;
}
//每个数作为一个节点，每次都有取和不取两种状态
//不取
dfs(i,j+1);
//取
if(!vis[i][j]){
save(i,j);
dfs(i,j+1);
restore(i,j);
}
}
int main(){
cin>>T;
while(T–){
ans=0;
sum=0;
cin>>N>>M;
memset(maze,0,sizeof(maze));
memset(vis,0,sizeof(vis));
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
cin>>maze[i][j];
}
}
sum=0;
dfs(1,1);
cout<<ans<<endl;
}
}
