当前位置：首页 > news >正文

C++：dfs，bfs各两则

news 来源：原创 2025/9/18 6:31:34

1.木棒

167. 木棒 - AcWing题库

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 5050 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

解题思路

我们先将所有木棒总长度与其中最长的木棍长度记录下来。将记录小木棍长度的数组排序，然后从最长的木棍枚举每根木棒可能的长度，优化：根据这个小木棒能不能被sum整除来进行第一次判断这个小木棒长度是否正确。进入bfs三个参数，u：构造了多少小木棍，cur：构造小木棍的长度，cnt：数组下标。

我们依次用断掉的木棍来凑出我们枚举的木棍长度并将当前枚举的木棍标记为已使用，当前木棍凑不出来就取消当前木棍的已使用标记，此处可进行一个优化：当第一个木棍与最后一个木棍搜索失败时，就一定搜不到了(第一个木棍搜不到了，那它就永远凑不出来了。最后一个也是，肯定是将前面的都用完之后再用的最后一个，不行肯定就是失败了) 优化：我们可以将长度相同的小木棍跳过，当当前凑的小木棍长度乘凑的小木棍根数等于木棒从长度时就return true; 当当前小木棍长度等于枚举的小木棍长度时就进入下一个小木棍的枚举。

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;int n;
int a[100];
int len=0,sum=0;
bool judge[100];
//u:构造了多少根小木棍,cur:构造小木棍的长度,cnt:数组下标
bool dfs(int u,int cur,int cnt)
{if(cur*u==sum)//凑够了{//由于初始传入的len所以当最后一次cur==len时，没有经过下面u+1，所以u是刚好的// cout<<"u: "<<u<<endl;// for(int i=0;i<n;i++)// cout<<judge[i]<<' ';// cout<<endl;return true;}if(cur==len)//这根木棍达到len了，换下一根木棍return dfs(u+1,0,0);for(int i=cnt;i<n;i++){if(judge[i])continue;if(cur+a[i]<=len){judge[i]=true;if(dfs(u,cur+a[i],i+1))return true;//直接成功judge[i]=false;//失败了，当没用过}//第一个木棍就搜索不到答案,或者//最后一个木棍搜索失败if(!cur||cur+a[i]==len){return false;}int j=i+1;while(j<n&&a[i]==a[j]) j++;i=j-1;//将重复的i跳过，排序的作用}return false;
}int main()
{while(scanf("%d",&n)&&n!=0){sum=0;len=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];//计算所有木棍总长度len=max(len,a[i]);//len肯定不能比零散的木棍小}memset(judge,false,sizeof(judge));sort(a,a+n,greater<int>());while(1){if(sum%len==0&&dfs(0,len,0))//传入len的话{cout<<len<<endl;break;}len++;}}return 0;
}

2. 飞机降落

4957. 飞机降落 - AcWing题库

有 NN 架飞机准备降落到某个只有一条跑道的机场。

其中第 ii 架飞机在 TiTi 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 DiDi 个单位时间，即它最早可以于 TiTi 时刻开始降落，最晚可以于 Ti+DiTi+Di 时刻开始降落。

降落过程需要 LiLi 个单位时间。

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断 NN 架飞机是否可以全部安全降落。

解题思路

我们可以用一个结构体来存储输入的到达的时刻与可以盘旋的时间与下降所需的时间(根据题目可以看出，下降所需时间不算在可以盘旋的时间里)我这里用pair<int,pair<int,int>>来存储的，看起来会麻烦些。

bool dfs参数：cnt来记录有多少飞机已经降落，ti表示当前的时刻(注意：会有当前时刻到达的飞机都降落完了，就要跳到下一个时间)

每一次都要从第一架飞机开始枚举，看如果当前这架飞机没有降落并且超过了到达时间+盘旋时间就失败了返回false，判断一下时间有没有到没有到就将时间改为降落时间(上面要用一个临时变量记录时间，这里改变的也是临时变量)然后看这架飞机没走过就将其标记为走过然后递归看这里让这架飞机飞能不能让飞机全飞完，不能就取消对这架飞机的标记。当降落的飞机==飞机总数时就返回true，根据返回值输出 YES或NO

AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int t;
int n;
pair<int,pair<int,int>> car[15];
bool st[15];//判断飞机是否降落//cnt判断有几架飞机降落了,ti是时间
bool dfs(int cnt,int ti)
{if(cnt==n) return true;for(int i=0;i<n;i++){int tmp=ti;//可能有的飞机没到点需要改成到的时刻if(!st[i]&&ti>car[i].first+car[i].second.first)//这一架没降落,并且时间超时return false;if(tmp<car[i].first)//现在没到i这架飞机的到达时刻tmp=car[i].first;if(!st[i]){st[i]=true;if(dfs(cnt+1,tmp+car[i].second.second)) return true;st[i]=false;}}return false;
}
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);//分别是到达的时刻，还能停留的时间，降落所需时间for(int i=0;i<n;i++)scanf("%d%d%d",&car[i].first,&car[i].second.first,&car[i].second.second);memset(st,false,sizeof st);if(dfs(0,0)) printf("YES\n");else printf("NO\n");}return 0;
}

3. 母亲的牛奶

1355. 母亲的牛奶 - AcWing题库

农夫约翰有三个容量分别为 A,B,CA,B,C 升的挤奶桶。

最开始桶 AA 和桶 BB 都是空的，而桶 CC 里装满了牛奶。

有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。

这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。

请你编写一个程序判断，当 AA 桶是空的时候，CC 桶中可能包含多少升牛奶，找出所有的可能情况。

解题思路

这几个桶只要有牛奶可以互相倒牛奶，只有两种可能把要倒的桶倒满或者把自己倒空

用一个结构体包含abc代表当前各个瓶子奶的容量，由于数据量很小所以我们可以用一个三维数组来存它的状态，创建一个队列存上面的结构体，枚举一个瓶子倒一个瓶子接(不能是同一个瓶子)，根据要倒牛奶瓶子的牛奶量和要接牛奶瓶子的剩余空间，来更新队列依次直到队列空。

我们遍历状态数组，输出所有当A瓶子为空时有过的C的值

AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
struct node
{int a,b,c;//记录当前a，b，c分别多少牛奶
};
int A,B,C;
bool st[25][25][25];//当值为true说明三个下标表示三个杯子分别盛的容量
queue<node> q;
int bfs(int a,int b,int c)
{q.push({a,b,c});//入队int val[3]={A,B,C};st[a][b][c]=true;while(!q.empty()){node t=q.front();q.pop();for(int i=0;i<3;i++)//枚举第i个桶向第j个桶里倒牛奶{for(int j=0;j<3;j++){if(i!=j)//不能自己给自己倒{int s[3]={t.a,t.b,t.c};if(s[i]==0)continue;//比较i个桶剩的牛奶，与第j桶还能放进去的牛奶，哪个更少int cmp=min(s[i],val[j]-s[j]);s[i]-=cmp;//i桶减去s[j]+=cmp;//j桶加上if(!st[s[0]][s[1]][s[2]]){st[s[0]][s[1]][s[2]]=true;q.push({s[0],s[1],s[2]});}}}}}
}int main()
{scanf("%d%d%d",&A,&B,&C);//分别能存储的容量bfs(0,0,C);for(int j=0;j<=C;j++){for(int i=0;i<=B;i++){if(st[0][i][j])printf("%d ",j);}}return 0;
}

4. 全球变暖

1233. 全球变暖 - AcWing题库

你有一张某海域 N×NN×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 22 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。

具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......
.......
.......
.......
....#..
.......
.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

解题思路

就是遍历所有的大陆，查看陆地数量与临海的陆地数量是否相同，其余就是普通的洪水覆盖模板

AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;int n;
char map[1010][1010];
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
queue<pair<int,int>> qu;
bool states[1010][1010];int cnt=0;
void bfs(int x,int y,int &sum1,int &sum2)
{qu.push({x,y});states[x][y]=true;while(!qu.empty()){auto t=qu.front();sum1++;qu.pop();bool falg=false;for(int i=0;i<4;i++){int a=t.first+dx[i];int b=t.second+dy[i];if(a<0||b<0||a>=n||b>=n) continue;if(states[a][b]) continue;//已经走过的if(map[a][b]=='.'){falg=true;//说明上一个邻海continue;}qu.push({a,b});states[a][b]=true;}if(falg) sum2++;//统计临海的数量}if(sum2==sum1)cnt++;}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){for(int j=0;j<n;j++){ cin>>map[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){ int cnt1=0;//记录岛屿边缘数量int cnt2=0;//记录岛屿陆地数量if(!states[i][j]&&map[i][j]=='#')bfs(i,j,cnt1,cnt2);}   }cout<<cnt<<endl;return 0;
}

1.木棒

解题思路

AC代码

2. 飞机降落

解题思路

AC代码

3. 母亲的牛奶

解题思路

AC代码

4. 全球变暖

解题思路

AC代码

相关文章：