DFS深度搜索学习--备战蓝桥杯版h
·
DFS深度优先搜索（暴搜）--栈
BFS宽度优先搜索 --队列（“最短距离”-bfs第一个搜到的点）--最小步数/距离/操作次数
dfs最重要的是找顺序
递推/递归/DFS
全排列型枚举
依次枚举每个位置应该放哪个数（用状态数组存状态）
指数型枚举
从1-n依次考虑每个选或者不选
组合型枚举
依次枚举每个位置放哪个数
练习1
P1036 [NOIP 2002 普及组] 选数 - 洛谷--组合型枚举例题
注意素数判断方法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=25;
int n,k;
int a[N];
int c[N];
int cnt=0;
bool check(int n) {
if(n<2)return false;
for(int i = 2; i * i <= n; i++) { // 只检查到 sqrt(n)
if(n % i == 0) return false;
}
return true;
}
void dfs(int x,int start)
{
if(x==k)
{
int sum=0;
for(int i=0;i<k;i++)
{
sum+=c[i];
}
if(check(sum))cnt++;
return;
}
for(int i=start;i<n;i++)
{
c[x]=a[i];
dfs(x+1,i+1);
c[x]=0;
}
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
dfs(0,0);
cout<<cnt<<endl;
return 0;
} 练习2
依次枚举每个位置上的调料数
#include<iostream>
using namespace std;
int n;
int a[10];
int count1=0;
void dfs1(int pos,int sum)
{
if(sum>n)return;
if(sum+(10-pos)*3<n)return;
if(sum+(10-pos)*1>n)return;
if(pos==10)
{
if(sum==n)count1++;
return;
}
for(int i=1;i<=3;i++)
{
dfs1(pos+1,sum+i);
}
}
void dfs2(int pos,int sum)
{
if(sum>n)return;
if(sum+(10-pos)*3<n)return;
if(sum+(10-pos)*1>n)return;
if(pos==10)
{
if(sum==n){
for(int i=0;i<10;i++)
{
cout<<a[i];
if(i<9)cout<<' ';
}
cout<<endl;
}
return;
}
for(int i=1;i<=3;i++)
{
a[pos]=i;
dfs2(pos+1,sum+i);
}
}
int main()
{
cin>>n;
dfs1(0,0);
cout<<count1<<endl;
if(count1!=0){
dfs2(0,0);
}
return 0;
}练习3
P1088 [NOIP 2004 普及组] 火星人 - 洛谷
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010;
int n,m;
int a[N];
int ans[N];
bool st[N];
int res;
bool return0=false;//剪枝条件
void dfs(int x)
{
if(return0)return;
if(x>n)
{
res++;
if(res==m+1)
{
return0=true;
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<' ';
}
}
return;
}
for(int i=1;i<=n;i++)
{
if(res==0)i=a[x];
if(!st[i])
{
st[i]=true;
ans[x]=i;
dfs(x+1);
st[i]=false;
ans[x]=0;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(0);
return 0;
}练习4
P1149 [NOIP 2008 提高组] 火柴棒等式 - 洛谷
要满足两个条件--A+B=C而且A火柴+B火柴+C火柴=n-4
依次位置选数
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010;
int n;
int a[N];
int res=0;
int nums[N]={6,2,5,5,4,5,6,3,7,6};
//计算火柴棍数量
int col(int x)
{
if(nums[x]>0)return nums[x];
int sumfire=0;
while(x)
{
sumfire+=nums[x%10];
x/=10;
}
return sumfire;
}
void dfs(int x,int sum)
{
if(sum>n)return;
if(x>3)
{
if(a[1]+a[2]==a[3]&&sum==n)
{
res++;
}
return;
}
for(int i=0;i<10010;i++)
{
a[x]=i;
dfs(x+1,sum+col(i));
a[x]=0;
}
}
int main()
{
cin>>n;
n-=4;
dfs(1,0);
cout<<res<<endl;
return 0;
}练习5
P2036 [COCI 2008/2009 #2] PERKET - 洛谷
依次列举每个位置的调料放还是不放
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15;
int n;
int ans=0x7f7f;
struct node{
int s,b;
}a[N];
void dfs(int x,int s1,int b1)
{
if(x>n)
{
if(s1==1&&b1==0)return;
ans=min(ans,abs(s1-b1));
return;
}
dfs(x+1,s1*a[x].s,b1+a[x].b);
dfs(x+1,s1,b1);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].s>>a[i].b;
}
dfs(1,1,0);
cout<<ans<<endl;
return 0;
}练习6
这个棋盘问题---依次列举每一行的位置上放不放以及放哪一列上
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10;
int n,k;
char g[N][N];
bool st[N];
int res;
int cnt=0;//记录当前放几个棋子
//x表示枚举到当前哪一行
void dfs(int x,int cnt)
{
if(cnt==k)
{
res++;
return;
}
if(x>=n)return;
//枚举列
for(int i=0;i<n;i++)
{
if(!st[i]&&g[x][i]=='#')//第i列没放过棋子且是#
{
st[i]=true;
dfs(x+1,cnt+1);
st[i]=false;
}
}
dfs(x+1,cnt);
}
int main()
{
while(cin>>n>>k&&n>0&&k>0){
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>g[i][j];
}
}
res=0;
dfs(0,0);
cout<<res<<endl;
}
return 0;
}
练习7
P1025 [NOIP 2001 提高组] 数的划分 - 洛谷
通过给的样例来看我们可以发现他很像组合型枚举（但是数是可以重复的）
于是一种方法就出来了----但是有两个测试样例会超时
通过nowsum进行剪枝
如果在当前位置nowsum加上后面位置的最大值都<n的话那么一定不会成功所以就提前剪枝
//组合型枚举
#include<iostream>
using namespace std;
const int N=25;
int n;
int r;
int a[N];
int st[N];
int cnt=0;
void dfs(int x,int start,int nowsum)
{
if(x>r)
{
if(nowsum==n)cnt++;
return;
}
for(int i=start;nowsum+i*(r-x+1)<=n;i++)
{
a[x]=i;
dfs(x+1,i,nowsum+i);
a[x]=0;
}
}
int main()
{
cin>>n>>r;
dfs(1,1,0);
cout<<cnt;
return 0;
} 练习8**
P1019 [NOIP 2000 提高组] 单词接龙（疑似错题） - 洛谷
这个题目稍微难一点用到了字符串的知识
看题目我们可以发现其实要满足两个条件
1.怎么判断一个单词能接到另一个单词的后面
这个我们可以用字符串的substr(开始位置，长度)截取字串来实现
2.怎么记录单词的使用次数（因为题目说每个单词最多只能用两次）数组used[i]表示次数
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=25;
int n;
string words[N];
int used[N];//记录每个单词的使用次数
int g[N][N];//存储第i个单词能否接到第j个单词的后面 ，g[i][j]就是两个单词重合的长度
int res=0;
void dfs(string d,int x)
{
res=max(res,(int)d.size());
used[x]++;
for(int i=0;i<n;i++)
{
if(g[x][i]&&used[i]<2)
{
dfs(d+words[i].substr(g[x][i]),i);
}
}
used[x]--;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>words[i];
}
char start;
cin>>start;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
string a=words[i];
string b=words[j];
for(int k=1;k<min(a.size(),b.size());k++)
{
if(a.substr(a.size()-k,k)==b.substr(0,k))
{
g[i][j]=k;
break;
}
}
}
}
for(int i=0;i<n;i++)
{
if(words[i][0]==start)
{
dfs(words[i],i);
}
}
cout<<res<<endl;
return 0;
}
迷宫问题
DFS 解决走迷宫问题的实现步骤：
数据结构准备：
①迷宫表示：使用二维数组
maze[m][n]存储迷宫的布局，0 或 1 表示通道或墙壁。②标记数组：使用
visited[m][n]标记节点是否已访问，避免重复访问。③方向数组：使用
dx[]和dy[]表示上下左右四个方向的偏移量，如dx = {-1, 0, 1, 0}，dy = {0, 1, 0, -1}，表示上、右、下、左四个方向的坐标变化。递归函数定义：
①dfs(int x, int y)是核心递归函数，其中x和y表示当前节点的坐标。②函数首先检查当前节点是否为终点，如果是则表示找到路径；然后检查是否越界、是否是墙壁或已访问，如果都不是，则标记为已访问，并递归调用
dfs函数对相邻节点进行搜索。搜索过程：
①从起点开始调用
dfs(start_x, start_y)。②对于当前节点
(x, y)，依次尝试向四个方向移动（根据dx和dy），并对满足条件（未越界、不是墙壁、未访问）的新节点调用dfs函数。③如果某一方向的递归调用找到了路径，返回
true，否则回溯，将当前节点标记为未访问（即取消标记），尝试其他方向。
练习1
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=25;
int n,m;
char g[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int cnt=0;
void dfs(int i,int j)
{
if(i<0||i>=n||j<0||j>=m||g[i][j]=='#')return;
g[i][j]='#';
cnt++;
for(int k=0;k<4;k++)
{
int x=i+dx[k];
int y=j+dy[k];
dfs(x,y);
}
}
int main()
{
cin>>m>>n;
int x=-1,y=-1;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>g[i][j];
if(g[i][j]=='@')
{
x=i,y=j;
}
}
}
dfs(x,y);
cout<<cnt<<endl;
return 0;
}练习2
P1596 [USACO10OCT] Lake Counting S - 洛谷
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int cnt=0;
char g[N][N];
bool st[N][N];
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,1,-1,1,-1};
void dfs(int i,int j)
{
if(i<0||i>=n||j<0||j>=m||g[i][j]=='.'||st[i][j])return;
st[i][j]=true;
for(int k=0;k<8;k++)
{
int x=i+dx[k];
int y=j+dy[k];
dfs(x,y);
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>g[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!st[i][j]&&g[i][j]=='W')
{
dfs(i,j);
cnt++;
}
}
}
cout<<cnt<<endl;
return 0;
}练习3
主要在于要设一个数组f[i][j]:表示（i,j）到（1,1）的距离
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=25;
int f[N][N];
int x1,y1,x2,y2;
int dx[12] = {-2, -2, -1, -1, 1, 1, 2, 2, -2, -2, 2, 2};
int dy[12] = {-1, 1, -2, 2, -2, 2, -1, 1, -2, 2, -2, 2};
void dfs(int x,int y,int sum)
{
if(x<=0||x>20||y<=0||y>20)return;
f[x][y]=sum;
for(int k=0;k<12;k++)
{
int i=x+dx[k];
int j=y+dy[k];
if(f[i][j]==0||f[i][j]>sum+1)
{
dfs(i,j,sum+1);
}
}
}
int main()
{
cin>>x1>>y1>>x2>>y2;
dfs(x1,y1,1);
cout<<f[1][1]-1<<endl;
memset(f,0,sizeof f);
dfs(x2,y2,1);
cout<<f[1][1]-1;
return 0;
}更多推荐
11
0- 0
已为社区贡献4条内容
所有评论(0)