void dfs(int depth)//depth表示当前的层数(或深度)
{
if(depth>n)//到达叶子节点，该路已走到尽头
return;
for(int i=1;i<=n;i++)//n表示最大的值，即最大深度为n
{
if(b[i]==0)//b数组表示探索的状态，1表示已被探索，0表示尚未被探索
{
b[i]=1;//标记当前的b[i]已被探索
a[level]=i;//记录当前的节点值
dfs(level+1);//进一步的搜索
b[i]=0;//还原当前的b[i]元素被探索的状态
}
}
}
数字型搜索
全排列问题
题目描述
排列与组合是常用的数学方法。
先给一个正整数 ( 1 < = n < = 10 )
例如n＝3，所有组合,并且按字典序输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
输入
输入一个整数n( 1<=n<=10)
输出
输出所有全排列
每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格）
样例输入 Copy
3
样例输出 Copy
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N=100;
typedef long long ll;
int n,a[10010],b[10010];
void print()
{
for(int i=1;i<=n;i++)
{
printf("%5d",a[i]);
}
cout<<endl;
}
void dfs(int level)
{
if(level==n+1)
{
print();
return;
}
for(int i=1;i<=n;i++)
{
if(b[i]==0)
{
b[i]=1;
a[level]=i;
dfs(level+1);
b[i]=0;
}
}
}
int main()
{
cin>>n;
dfs(1);
}
【牛客】 Factorial
1、暴力解题，代码略；
2、dfs解题(重点)，万物皆可搜，有点类似斐波那契递归
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
#define IO ios::sync_with_stdio(false), cin.tie(0)
#define T int t ;cin >> t;while(t--)
ll a[maxn];
ll dfs(ll n)
{
if(n<=1)
{
return 1;
}
else
{
return dfs(n-1)*n;
}
}
int main()
{
T
{
ll n;
scanf("%lld",&n);
printf("%lld\n",dfs(n));
}
}
地图型搜索
n皇后问题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,y[100010],s,ans[100010];
bool check(int x)//剪枝，判断两点的位置\\
两点的斜率的绝对值不得等于1；两点不得在同一水平线上(包括同一行和同一列)
{
for(int i=1;i<x;i++)//i本身就是指行号，y[i]表示对应的列号
{
if(abs(x-i)==abs(y[x]-y[i])||y[x]==y[i]||x==i)
{
return 0;
}
}
return 1;
}
void dfs(int num)
{
if(num>n)//越界处理
{
s++;
return;
}
for(int i=1;i<=n;i++)
{
y[num]=i;//将当前的行号赋值给第num个皇后
if(check(num))
dfs(num+1);//进行下一步的搜索
}
}
int main()
{
for(int i=1;i<=10;i++)
{
n=i;
s=0;
dfs(1);
ans[i]=s;
}
while(~scanf("%d",&n)&&n)
printf("%d\n",ans[n]);
}
POJ3083 Children of the Candy Corn
左搜索(Ldfs)+右搜索(Rdfs)+最短路径搜索(bfs)
搜索方位
左搜索：
始终靠左搜索，如果左边是墙#，那就往上面搜索；上面是墙#，那就往右边搜索；右边是墙#则返回之前的位置，即往后搜索。
右搜索：
bfs最短路搜索：
创建队列，在一个点的周围的同一层搜索(这是与DFS的区别最大之处)，用vis数组标记是否被搜索过
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=55;
char mp[41][41];
int vis[41][41];
int m,n,f,ans1,ans2;
int head_x,head_y,tail_x,tail_y;
int dir1[4][2]= {-1,0,1,0,0,1,0,-1};
struct node
{
int x,y,step;
} head,tail;
bool judge(int xx,int yy)
{
if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&mp[xx][yy]!='#'&&vis[xx][yy]==0)
return true;
return false;
}
void dfs1(int xx,int yy,int step,int dir)//逆时针走法
{
if(f==1)
return;
if(xx==tail_x&&yy==tail_y)
{
f=1;
ans1=step;
return;
}
if(dir==1)//右上左下
{
if(judge(xx+1,yy)) dfs1(xx+1,yy,step+1,4);
if(judge(xx,yy-1)) dfs1(xx,yy-1,step+1,1);
if(judge(xx-1,yy)) dfs1(xx-1,yy,step+1,2);
if(judge(xx,yy+1)) dfs1(xx,yy+1,step+1,3);
}
else if(dir==2)//上左下右
{
if(judge(xx,yy-1)) dfs1(xx,yy-1,step+1,1);
if(judge(xx-1,yy)) dfs1(xx-1,yy,step+1,2);
if(judge(xx,yy+1)) dfs1(xx,yy+1,step+1,3);
if(judge(xx+1,yy)) dfs1(xx+1,yy,step+1,4);
}
else if(dir==3)//左下右上
{
if(judge(xx-1,yy)) dfs1(xx-1,yy,step+1,2);
if(judge(xx,yy+1)) dfs1(xx,yy+1,step+1,3);
if(judge(xx+1,yy)) dfs1(xx+1,yy,step+1,4);
if(judge(xx,yy-1)) dfs1(xx,yy-1,step+1,1);
}
else//右下上左
{
if(judge(xx,yy+1)) dfs1(xx,yy+1,step+1,3);
if(judge(xx+1,yy)) dfs1(xx+1,yy,step+1,4);
if(judge(xx,yy-1)) dfs1(xx,yy-1,step+1,1);
if(judge(xx-1,yy)) dfs1(xx-1,yy,step+1,2);
}
}
void dfs2(int xx,int yy,int step,int dir)
{
if(f==1)
{
return;
}
if(xx==tail_x&&yy==tail_y)
{
f=1;
ans2=step;
return;
}
if(dir==1)
{
if(judge(xx-1,yy)) dfs2(xx-1,yy,step+1,2);
if(judge(xx,yy-1)) dfs2(xx,yy-1,step+1,1);
if(judge(xx+1,yy)) dfs2(xx+1,yy,step+1,4);
if(judge(xx,yy+1)) dfs2(xx,yy+1,step+1,3);
}
else if(dir==2)
{
if(judge(xx,yy+1)) dfs2(xx,yy+1,step+1,3);
if(judge(xx-1,yy)) dfs2(xx-1,yy,step+1,2);
if(judge(xx,yy-1)) dfs2(xx,yy-1,step+1,1);
if(judge(xx+1,yy)) dfs2(xx+1,yy,step+1,4);
}
else if(dir==3)
{
if(judge(xx+1,yy)) dfs2(xx+1,yy,step+1,4);
if(judge(xx,yy+1)) dfs2(xx,yy+1,step+1,3);
if(judge(xx-1,yy)) dfs2(xx-1,yy,step+1,2);
if(judge(xx,yy-1)) dfs2(xx,yy-1,step+1,1);
}
else
{
if(judge(xx,yy-1)) dfs2(xx,yy-1,step+1,1);
if(judge(xx+1,yy)) dfs2(xx+1,yy,step+1,4);
if(judge(xx,yy+1)) dfs2(xx,yy+1,step+1,3);
if(judge(xx-1,yy)) dfs2(xx-1,yy,step+1,2);
}
}
int bfs()
{
queue<node> q;
while(!q.empty())
{
q.pop();
}
head.x=head_x,head.y=head_y,head.step=1;
q.push(head);
vis[head_x][head_y]=1;
while(!q.empty())
{
head=q.front();
q.pop();
if(head.x==tail_x&&head.y==tail_y)
{
return head.step;
}
for(int i=0; i<4; i++)
{
tail.x=head.x+dir1[i][0];
tail.y=head.y+dir1[i][1];
if(judge(tail.x,tail.y))
{
tail.step=head.step+1;
vis[tail.x][tail.y]=1;
q.push(tail);
}
}
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,0,sizeof vis);
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
{
scanf(" %c",&mp[i][j]);
if(mp[i][j]=='S')
{
head_x=i;
head_y=j;
}
if(mp[i][j]=='E')
{
tail_x=i;
tail_y=j;
}
}
}
f=0;
ans1=0;
dfs1(head_x,head_y,1,1);
f=0;
ans2=0;
dfs2(head_x,head_y,1,1);
int ans3=bfs();
printf("%d %d %d\n",ans1,ans2,ans3);
}
}
棋盘问题
n表示棋盘的大小是n*n，m表示棋子的数量，结束dfs的条件就是当前的棋子数量大于等于m(因为初始的0就已经存在1颗棋子了)。
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#define IO ios::sync_with_stdio(false), cin.tie(0)
typedef long long ll;
using namespace std;
const ll maxn=1e5+10;
char mp[100][100];
bool vis[100];
ll n,m,s;
void dfs(ll x,ll y)
{
if(y>=m)
{
s++;
return;
}
for(ll i=x; i<n; i++)
for(ll j=0; j<n; j++)
{
if(vis[j]==false&&mp[i][j]=='#')
{
vis[j]=true;
dfs(i+1,y+1);
vis[j]=false;
}
}
}
int main()
{
while(1)
{
scanf("%lld%lld",&n,&m);
if(n==-1&&m==-1)
break;
memset(vis,0,sizeof vis);
memset(mp,0,sizeof mp);
for(ll i=0; i<n; i++)scanf("%s",mp[i]);
s=0;
dfs(0,0);
cout<<s<<endl;
}
}
Oil Deposit
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
ll m,n;
char mp[110][110];
ll dir[8][2]= { {0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1} };//方向可以任意，当前方向见图
void dfs(ll x,ll y)
{
mp[x][y]='*';//把当前的@转换成*，避免重复查找
for(ll i=0; i<8; i++)
{
ll xx=x+dir[i][0],yy=y+dir[i][1];
if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&mp[xx][yy]=='@')
{
dfs(xx,yy);
}
}
return;//递归结束
}
int main()
{
while(~scanf("%lld%lld",&m,&n)&&n&&m)
{
ll sum=0;
for(ll i=1; i<=m; i++)
{
for(ll j=1;j<=n;j++)
{
cin>>mp[i][j];
//scanf(" %c",&mp[i][j]);
//两种读入方式均可，要注意的是，用scanf()读入的话，需要在%c之前加入一个空格，这是专门用来吸收"\n"
}
}
for(ll i=1; i<=m; i++)
{
for(ll j=1; j<=n; j++)
{
if(mp[i][j]=='@')
{
dfs(i,j);
sum++;
}
}
}
cout<<sum<<endl;
}
}
Red and Black
用dfs搜索最长路，黑砖可走，红砖不可走，@表示出发点，输出最大黑砖数
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
typedef long long ll;
ll m,n;
char mp[25][25];
ll dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} };
ll s;
void dfs(ll x,ll y)
{
ll xx,yy;
for(ll i=0;i<4;i++)
{
xx=x+dir[i][0];
yy=y+dir[i][1];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]!='#')
{
s++;
mp[xx][yy]='#';
dfs(xx,yy);
}
}
}
int main()
{
while(~scanf("%lld %lld",&m,&n)&&m&&n)
{
ll xx,yy;
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
scanf(" %c",&mp[i][j]);
if(mp[i][j]=='@')
{
xx=i;
yy=j;
}
}
}
s=1;
mp[xx][yy]='#';
dfs(xx,yy);
cout<<s<<endl;
}
}
P1162 填涂颜色
建议从1开始读入，因为这样有一个好处，能够建立起天然的下标为0的围墙数组，可以防止数组下标小于0，以至于越界
dfs1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
ll n;
ll mp[35][35];
ll vis[35][35];
ll dir[4][2]= { {-1,0},{1,0},{0,-1},{0,1} };
void dfs(ll x,ll y)
{
if(x==0||y==0||x>n||y>n)
return;
for(ll i=0; i<4; i++)
{
ll xx=x+dir[i][0],yy=y+dir[i][1];
if(mp[xx][yy]!=1&&xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy])
{
vis[xx][yy]=1;
dfs(xx,yy);
}
}
}
int main()
{
memset(vis,0,sizeof vis);
memset(mp,0,sizeof mp);
scanf("%lld",&n);
for(ll i=1; i<=n; i++)
{
for(ll j=1; j<=n; j++)
{
cin>>mp[i][j];
}
}
for(ll i=1;i<=n;i++)
{
if(mp[1][i]==0)
dfs(1,i);
if(mp[i][1]==0)
dfs(i,1);
if(mp[n][i]==0)
dfs(n,i);
if(mp[i][n]==0)
dfs(i,n);
}
for(ll i=1; i<=n; i++)
{
for(ll j=1; j<=n; j++)
{
if(j>1)
cout<<' ';
if(mp[i][j]!=1&&!vis[i][j])
mp[i][j]=2;
cout<<mp[i][j];
}
cout<<endl;
}
}
dfs2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mp[35][35];
ll n;
ll dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} };
void dfs(ll x,ll y)
{
mp[x][y]=3;
for(ll i=0;i<4;i++)
{
ll xx=x+dir[i][0],yy=y+dir[i][1];
if(xx>=0&&yy>=0&&xx<=n+1&&yy<=n+1&&mp[xx][yy]==0)
{
dfs(xx,yy);
}
}
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=n;j++)
{
cin>>mp[i][j];
}
}
dfs(0,0);
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=n;j++)
{
if(j>1)
{
cout<<' ';
}
if(mp[i][j]==3)
{
mp[i][j]=0;
}
else if(mp[i][j]==0)
{
mp[i][j]=2;
}
cout<<mp[i][j];
}
cout<<endl;
}
}
ganmao病毒被消灭
关键代码就两行，还有一个暗坑
关键代码：
if(sum+a[xx][yy]>=dp[xx][yy]||xx<1||yy<1||xx>n||yy>n||vis[xx][yy]||!a[xx][yy])continue;
dp[xx][yy]=sum+a[xx][yy];
当你已经找到一条较小的路径之后，那么从上一个点出发，其他路径都没有必要再将较大的路径赋值给这条较小的路径，可以直接continue。
暗坑：
如果被一排或者一行的0挡住那么输出0，最好的方法就是定义一个全局的flag标记，如果flag等于1则表示有结果，否则输出0。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
ll a[105][105];
ll dir[4][2]= { {-1,0},{1,0},{0,-1},{0,1} };
bool vis[105][105]= {0};
ll dp[105][105];
ll s=inf;
ll n;
ll flag=0;
void dfs(ll x,ll y,ll sum)
{
if(x==n&&y==n)
{
s=min(s,sum);
flag=1;
return;
}
for(ll i=0; i<4; i++)
{
ll xx=x+dir[i][0],yy=y+dir[i][1];
if(sum+a[xx][yy]>=dp[xx][yy]||xx<1||yy<1||xx>n||yy>n||vis[xx][yy]||!a[xx][yy])continue;
dp[xx][yy]=sum+a[xx][yy];
vis[xx][yy]=1;
dfs(xx,yy,sum+a[xx][yy]);
vis[xx][yy]=0;
}
}
int main()
{
scanf("%lld",&n);
for(ll i=1; i<=n; i++)
{
for(ll j=1; j<=n; j++)
{
scanf("%lld",&a[i][j]);
}
}
memset(vis,0,sizeof vis);
memset(dp,inf,sizeof dp);
vis[1][1]=1;
dp[1][1]=a[1][1];
dfs(1,1,a[1][1]);
if(flag)
printf("%lld\n",s);
else
printf("0\n");
return 0;
}
最小路径和
核心代码仍然是上题的两行，且无暗坑，且仅有两个方向:右和下，代码就别到leetcode上交了，主要是为了学习dfs那两行核心代码的作用
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e3+10;
const ll inf=0x3f3f3f3f;
ll m,n;
ll mp[maxn][maxn],vis[maxn][maxn];
ll s=inf;
ll dp[maxn][maxn];
ll dir[2][2]={ {1,0},{0,1} };
void dfs(ll x,ll y,ll sum)
{
if(x==m&&y==n)
{
s=min(s,sum);
return;
}
for(ll i=0;i<2;i++)
{
ll xx=x+dir[i][0],yy=y+dir[i][1];
if(xx<1||yy<1||xx>m||yy>n||sum+mp[xx][yy]>=dp[xx][yy])continue;
dp[xx][yy]=sum+mp[xx][yy];
vis[xx][yy]=1;
dfs(xx,yy,sum+mp[xx][yy]);
vis[xx][yy]=0;
}
}
int main()
{
scanf("%lld%lld",&m,&n);
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
scanf("%lld",&mp[i][j]);
}
}
memset(vis,0,sizeof vis);
memset(dp,inf,sizeof dp);
vis[1][1]=1;
dp[1][1]=mp[1][1];
dfs(1,1,mp[1][1]);
printf("%lld\n",s);
}
P1451 求细胞数量（连通块个数）
数字1-9表示存在细胞，把当前位置赋值为0，默认视作不存在细胞，本次搜索完之后，无需将原先位置的数还原。
#include <bits/stdc++.h>
#define sc2(a,b) scanf("%lld%lld", &a,&b)
#define mem(a) memset(a,false,sizeof a)
using namespace std;
typedef long long ll;
ll n,m;
ll s=0;
ll a[105][105];
ll dir[4][2]={ {-1,0},{1,0},{0,1},{0,-1} };
void dfs(ll x,ll y)
{
if(x<=0||y<=0||x>n||y>m)return;
a[x][y]=0;
for(ll i=0;i<4;i++)
{
ll xx=x+dir[i][0],yy=y+dir[i][1];
if(a[xx][yy])
{
dfs(xx,yy);
}
}
}
int main()
{
sc2(n,m);
s=0;
mem(a);
mem(vis);
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
scanf("%1lld",&a[i][j]);
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
if(a[i][j])
s++,
dfs(i,j);
}
}
printf("%lld\n",s);
}
-------------------------------------------------------------------------------------------------------------