林大超市买水果
Description
林大的超市有N种水果,18级的新生小王同学兜里有M元钱,想买K种水果,但他想刚刚把M元钱花完,有这个可能吗?
Input
第一行输入M,N,K含义如上;(1<=M<=1e8,1<=n<=30,1<=k<=8)
接下来是每种水果的价格;
Output
如果可以的话,输出Yes;
否则输出No;
Sample Input
20 5 3
1 2 3 15 6
Sample Output
Yes
题解
这题比较有趣,小王想要买水果,(每样水果只能买一个),怎样才能刚好把钱花完然后还要买到自己需要的数量。
我最开始是想要利用二进制枚举来写的,但是却卡了时间,因为数据已经开到30了,所以过不了,后来我又换了深搜,结果也没过(TLE),仔细分析题面,发现也只有广搜有戏了,但是广搜的话就不想是以前写的那些题那样直接套模板了,需要有点变通
我们来看一下广搜的实质吧,这里画了张草图:
一层一层的搜索下去(一件商品一件商品的浏览),直到出现满足的条件或者商品浏览完
对于每种水果只有两种状态——买或者不买,所以有:
//买这件水果
todo.push({cur+1,number+1,money-price[cur]});
浏览了这件商品自然cur要加一,因为买了,所以number+1,并且钱要减少,所以money-price[cur]
//不买这件水果
todo.push({cur+1,number,money});
因为只做了浏览,所以cur+1就行了
决定是否符合要求的也只有两个条件——钱用完并且买到足够的商品,因此有:
if (money==0&&number==want) return 1;
综上,有AC代码:
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-09 21:08:23
* @Website1: https://449293786.site
* @原创代码,版权所有,转载请注明原作者
*/
#include<bits/stdc++.h>
using namespace std;
struct node
{
int cur;
//当前查找的商品
int number;
//已经购买的商品
int money;
//还剩的钱
};
queue <node> todo;
int price[35],want,all;
int bfs(int money)
{
todo.push({0,0,money});
while (!todo.empty())
{
node tmp=todo.front();
todo.pop();
int cur=tmp.cur;
int number=tmp.number;
int money=tmp.money;
//读取每个节点的状态
if (money==0&&number==want) return 1;
//如果钱刚好花完并且买足了了自己想要的商品,就返回真
if (money-price[cur]>=0&&number<want&&cur<all)
{
todo.push({cur+1,number+1,money-price[cur]});
//买,则钱变少,数量变多
todo.push({cur+1,number,money});
//不买,钱不变,数量不变,跳过当前商品
}
}
return 0;
}
int main()
{
int money;
cin>>money>>all>>want;
for (int i=0;i<all;i++)
scanf("%d",&price[i]);
bfs(money)==1?printf("Yes\n"):printf("No\n");
return 0;
}
最大黑色区域-搜索
Description
二值图像是由黑和白两种像素组成的矩形点阵,图像识别的一个操作是求出图像中最大黑区域的面积。请设计一个程序完成二值图像的这个操作。黑区域由黑像素组成,一个黑区域中的每像素至少与该区域中的另一像素相邻,规定一个像素仅与其上、下、左、右的像素相邻。两个不同的黑区域没有相邻的像素。一个黑区域的面积是其所包含的像素数。
Input
第 1 行含两个整数 n 和 m,1≤n、m≤100,分别表示二值图像的行数与列数。后面n行,每行含m个整数0或1,其中第i行表示图像的第i行的m个像素,0表示白像素,1 表示黑像素。每行中的两个数之间用一个空格分隔。
Output
输出一行一个数,表示相应的图像中最大黑区域的面积。
Sample Input
5 6
0 1 1 0 0 1
1 1 0 1 0 1
0 1 0 0 1 0
0 0 0 1 1 1
1 0 1 1 1 0
Sample Output
7
这题没什么好说的,只是为了留个广搜模板罢了
AC代码:
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-04-05 22:43:42
* @Website1: 449293786.site
*/
#include<bits/stdc++.h>
using namespace std;
struct node {
int x;
int y;
};
queue<node>todo;
queue<node>bg;
int n,m;
int x2[5]={1,-1,0,0};
int y2[5]={0,0,1,-1};
int maps[105][105];
int walked[105][105];
//creat a map
int bfs(int bx,int by){
int ans=0;
maps[bx][by]=0;
todo.push({bx,by});
while(!todo.empty()){
node tmp;
tmp=todo.front();
todo.pop();
ans++;
int x3=tmp.x;
int y3=tmp.y;
// cout<<x3<<" "<<y3<<endl;
for (int i=0;i<4;i++){
int x=x2[i]+x3;
int y=y2[i]+y3;
if (x>=0&&x<n&&y>=0&&y<m&&maps[x][y]==1){
todo.push({x,y});
maps[x][y]=0;
}
}
}
return ans;
}
int main(){
int ans=0;
int bx,by;
//load the map
cin>>n>>m;
for(int i=0;i<n;i++){
for (int j=0;j<m;j++){
scanf("%d",&maps[i][j]);
if (maps[i][j]){
bg.push({i,j});
}
}
}
while(!bg.empty()){
node tmp=bg.front();
bg.pop();
if (maps[tmp.x][tmp.y]){
int res=bfs(tmp.x,tmp.y);
ans=max(res,ans);
}
}
cout<<ans<<endl;
return 0;
}
出处:https://grimoire.cn/acm/409-bfs.html
版权:本文《4.09广搜题解》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任