蓝桥杯-dfs搜索模板题（一）
- P2089 烤鸡
- P1088 火星人
- P1149 火柴棒等式
- P2036 PERKET
- P1135 奇怪的电梯
- 结语
P2089 烤鸡
对于每个位置枚举数字
#include<bits/stdc++.h>
using namespace std;
const int N=10+10;
int n;
int arr[N];//临时方案
int res=0;//方案数
int mem[1000000][N];//所有方案
void dfs(int x,int sum)//x是位数，sum是已选的总质量
{
if(sum>n)return;
if(x>10)
{
if(sum==n)
{
res++;
for(int i=1;i<=10;i++)
{
mem[res][i]=arr[i];
}
}
return;
}
for(int i=1;i<=3;i++)
{
arr[x]=i;
dfs(x+1,sum+i);
arr[x]=0;
}
}
int main()
{
scanf("%d",&n);
dfs(1,0);
printf("%d\n",res);
for(int i=1;i<=res;i++)
{
for(int j=1;j<=10;j++)
{
printf("%d ",mem[i][j]);
}
printf("\n");
}
return 0;
}
P1088 火星人
本质也是对着位置枚举数字但是是在火星人给定的基础上，不然要搜索的太多了会爆
#include<bits/stdc++.h>
using namespace std;
int n, m, res;
const int N = 10010;
int arr[N];
int mars[N];
bool st[N];
bool return0 = false;
void dfs(int x)
{
if (return0)return;//找到之后就不用往后搜了
//跟上面那个不一样，这个位数最多有10000太多了不能全部遍历
if (x > n)
{
res++;
if (res == m + 1)
{
return0 = true;
for (int i = 1; i <= n; i++)
{
cout << arr[i] << ' ';
}
}
return;
}
for (int i = 1; i <= n; i++)
{
if (!res)
{
i = mars[x];//从火星人给的开始枚举
}
if (!st[i])
{
st[i] = true;
arr[x] = i;
dfs(x + 1);
st[i] = false;
arr[x] = 0;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> mars[i];
dfs(1);
return 0;
}
P1149 火柴棒等式
按照题目要求去搜索暴力。
经验之谈，最多应是711,多试几个可以试出来
#include<bits/stdc++.h>
using namespace std;
const int N= 10010;
int n;
int arr[N];
int res=0;
int nums[N]={6,2,5,5,4,5,6,3,7,6};//存火柴棍
int col(int x)//计算火柴棍数量
{
if(nums[x]) return nums[x];
else
{
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(arr[1]+arr[2]==arr[3]&&sum==n)
{
res++;
}
return;
}
for(int i=0;i<=1000;i++)
{
arr[x]=i;
dfs(x+1,sum+nums[i]);
arr[x]=0;
}
}
int main()
{
cin>>n;
n-=4;
for(int i=10;i<=1000;i++)
{
nums[i]=nums[i%10]+nums[i/10];
}
dfs(1,0);
cout<<res;
return 0;
}
P2036 PERKET
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n;
int acid[N],bitter[N];
int res=1e9;//存答案
int st[N];//0未考虑 1选2不选
void dfs(int x)
{
if(x>n)
{
bool has=false;
int sum1=1;//酸度之积
int sum2=0;//苦度之和
for(int i=1;i<=n;i++)
{
if(st[i]==1)
{
has=true;
sum1*=acid[i];
sum2+=bitter[i];
}
}
if(has) res=min(res,abs(sum1-sum2));//有得选才走，啥都不选返回1没价值
return ;
}
//选
st[x]=1;
dfs(x+1);
st[x]=0;
//不选
st[x]=2;
dfs(x+1);
st[x]=0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>acid[i]>>bitter[i];
dfs(1);
cout<<res;
return 0;
}
P1135 奇怪的电梯
每层只走一次的方案一定比每次重复走的方案好，用st来记录有没有走过。
这道题用以下代码只能过一部分，也是暴力的局限之处。得有更好的优化或其他方法
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,A,B;
int evlt[N];
int res=1e9;
bool st[N];
//当前在x楼，按了cnt次按钮
void dfs(int x,int cnt)
{
if(cnt>=res)return;
if(x>n||x<0)return ;
if(x==B)
{
res=min(res,cnt);
return ;
}
//上
if(x+evlt[x]<=n&&!st[x+evlt[x]])
{
st[x+evlt[x]]=true;
dfs(x+evlt[x],cnt+1);
st[x+evlt[x]]=false;
}
//下
if(x-evlt[x]>0&&!st[x-evlt[x]])
{
st[x-evlt[x]]=true;
dfs(x-evlt[x],cnt+1);
st[x-evlt[x]]=false;
}
}
int main()
{
cin>>n>>A>>B;
for(int i=1;i<=n;i++)
{
cin>>evlt[i];
}
dfs(A,0);
if(res==1e9)
{
cout<<-1;
return 0;
}
cout<<res;
return 0;
}
结语
整理自链接: link
