优美的大乔 2023-02-18 11:43 采纳率: 94.7%
浏览 49
已结题

一个蒟蒻提出的关于bfs或dfs的问题C++

识别水果
题目描述:
在海上漂泊了249天后,由于食物和水都已消耗光了,三人已是筋疲力尽。终于,在第250天的早晨,一个隐隐约约的黑点在远处出现了,是一个小岛,三大护法高兴的几乎要跳起来。于是下令舰队全速前进,驶向小岛。
在登陆后,他们才知道,这就是著名的移花岛,岛上有三位女神:dp女神、涓涓女神和紫晶女神。由于三大女神与holy_one的关系不错,因此高兴地接待了他们三人。由于看到三人饥渴难耐,负责岛上水果的涓涓女神便带他们去了果园。
果园里水果丰富,共有n个,它们的标号为1~n,但有些水果是有毒,而且水果与水果之间有藤蔓相连,如果一个水果有毒,那么所有与它相连的所有水果都是有毒的。其中m个水果上面会贴着一个标签,从标签上可以看出这个水果是否有毒。当然,如果这个水果的标签显示无毒,但它与有毒的水果相连,那它也是有毒的。
为帮助三人尽快吃到水果,涓涓女神给了他们一张毒物字典,只有通过字典上的对应关系翻译后,才能知道水果是否有毒。转化后的名称中包含‘poison’,即表示这个水果有毒。
输入格式:
第一行,字符串a
第二行,字符串b
a串和b串长度都是26,a[i]到b[i]表示两个字母的对应关系。注意,对应关系是单向的。
两个整数n和m(m<=n<=10000)。
以下m行,每行第一个数是水果的标号k,后面是第k个水果的标签s,k和s之间有空格分隔开,标签长度小于255。
一个整数p。
以下p行,每行两个整数x,y 表示第x个水果和第y个水果之间有藤蔓相连。
输出格式:
无毒的水果的个数。
样例输入:

jgltnkyvhefdoszmcwqarixupb
ibtoupqadsxkcmrynhzegwljvf
10 6
6 awg
1 nij
3 ktjetcjip
7 nim
2 gqv
10 ktjetczfw
4
1 2
1 7
3 2
10 8

样例输出:

4

各位神犇,这道题目要用bfs还是dfs啊,总感觉是bfs的变种……传送门

  • 写回答

3条回答 默认 最新

  • 睿智的聪大明 2023-02-18 21:24
    关注

    我是用BFS的。。。
    AC解题代码:

    
    #include<bits/stdc++.h>
    using namespace std;
    map<char,char>b;
    string s,s1,s2;
    int n,m,p,x,sum,y,h[10001];
    bool g[10001][10001];
    queue<int>q;
    void bfs()
    {
        while(!q.empty())
        {
            sum++;
            int a=q.front();
            q.pop();
            for(int i=1;i<=n;i++)
            {
                if(g[a][i]==1&&h[i]==0)
                {
                    h[i]=1;
                    q.push(i);
                }
            }
        }
    }
    int main()
    {
         cin>>s1>>s2;
         for(int i=0;i<26;i++)
        {
            b[s1[i]]=s2[i];
        }
         cin>>n>>m;
         for(int i=1;i<=m;i++)
         {
             cin>>x>>s;
             for(int j=0;j<s.size();j++) s[j]=b[s[j]];//解密字符串
            if(int(s.find("poison"))!=-1)//判断是否有毒
            {
                q.push(x);
                h[x]=1;
            }
        }
        cin>>p;
        for(int i=1;i<=p;i++)
        {
            cin>>x>>y;
            g[x][y]=g[y][x]=1;
        }//保存图
        bfs();//广搜
        cout<<n-sum;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 3月5日
  • 已采纳回答 2月25日
  • 创建了问题 2月18日

悬赏问题

  • ¥15 ghpython这里总是报错而且rhino视图窗口内不显示怎么办
  • ¥15 布尔运算推导,请证明
  • ¥15 有没有人会打学生成绩管理系统呀
  • ¥15 在使用Fiddler和夜神模拟器抓包的时候一直出现443该怎么办啊QAQ搜了好几个笔记都没有解决
  • ¥15 3x7的二维数组A、B、C,A中的任意1个数组元素与B的任意1个数组元素、同时又与C的任意1个数组元素比较,把不同位置出现相同数的比较称为无意义,反之称为有意义,把有意义的比较打印输出。
  • ¥20 预测模型怎么处理原始数据(随机森林)
  • ¥20 请问discuz3.5如何实现插入ckplayer全能播放器功能呢?
  • ¥15 thingsboard代码编译出错误
  • ¥15 博途v18仿真报错怎么解决
  • ¥15 欧姆龙plc枕式包装机 ST编程