MENU

4.09广搜题解

April 9, 2020 • 题解

林大超市买水果

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),仔细分析题面,发现也只有广搜有戏了,但是广搜的话就不想是以前写的那些题那样直接套模板了,需要有点变通

我们来看一下广搜的实质吧,这里画了张草图:

tiny-540-2020-04-09-21-20-00

一层一层的搜索下去(一件商品一件商品的浏览),直到出现满足的条件或者商品浏览完

对于每种水果只有两种状态——买或者不买,所以有:

//买这件水果
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;
}
作者:NorthCity1984
出处:https://grimoire.cn/acm/409-bfs.html
版权:本文《4.09广搜题解》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任

Last Modified: April 22, 2020