廣度優先搜索練習之(zhī)神奇的(de)電梯 - 新聞資訊 - 雲南小程序開發|雲南軟件開發|雲南網站建設-昆明融晨信息技術有限公司

159-8711-8523

雲南網建設/小程序開發/軟件開發

知識

不(bù)管是(shì)網站,軟件還是(shì)小程序,都要(yào / yāo)直接或間接能爲(wéi / wèi)您産生價值,我們在(zài)追求其視覺表現的(de)同時(shí),更側重于(yú)功能的(de)便捷,營銷的(de)便利,運營的(de)高效,讓網站成爲(wéi / wèi)營銷工具,讓軟件能切實提升企業内部管理水平和(hé / huò)效率。優秀的(de)程序爲(wéi / wèi)後期升級提供便捷的(de)支持!

您當前位置>首頁 » 新聞資訊 » 技術分享 >

廣度優先搜索練習之(zhī)神奇的(de)電梯

發表時(shí)間:2020-10-19

發布人(rén):融晨科技

浏覽次數:40

Description
有一座已知層數爲(wéi / wèi)n的(de)高樓,這(zhè)座高樓的(de)特殊之(zhī)處在(zài)于(yú)隻能靠電梯去上(shàng)下樓,所以(yǐ)要(yào / yāo)去到(dào)某一層要(yào / yāo)非常耽誤時(shí)間,然而(ér)更悲哀的(de)是(shì),這(zhè)座高樓的(de)電梯是(shì)限号的(de),小鑫最開始的(de)時(shí)候在(zài)1層,他(tā)想去第x層,問題是(shì)他(tā)最起碼要(yào / yāo)經過多少層(包含第x層)才能到(dào)達第x層。
Input
多組輸入。
第一行是(shì)三個(gè)正整數n,m,q。分别代表樓的(de)總層數,給定的(de)m條信息和(hé / huò)q次查詢。
接下來(lái)的(de)m行,每行的(de)第一個(gè)整數pos代表這(zhè)是(shì)第pos層的(de)電梯,第二個(gè)數代表從這(zhè)一層可以(yǐ)去的(de)樓層總共有num個(gè),之(zhī)後的(de)num個(gè)數字代表從第pos層代表可以(yǐ)去的(de)樓層。
最後的(de)q行,每行一個(gè)整數代表小鑫想去的(de)樓層号碼。
1<=m,pos,num<=n<=200
1<=q<=20
Output
對于(yú)每次詢問輸出(chū)一個(gè)整數,占一行。代表如果要(yào / yāo)去某個(gè)樓層最少要(yào / yāo)經過多少層,如果到(dào)不(bù)了(le/liǎo)的(de)話就(jiù)輸出(chū)-1。
Sample
Input
10 4 3
1 2 6 7
3 4 4 6 8 10
5 2 2 3
7 3 10 5 6
4
5
9
Output
5
3
-1
這(zhè)是(shì)AC代碼,後面有一個(gè)wrong answer代碼,求大(dà)佬指點

#include<bits/stdc++.h>
using namespace std;
int a[300][300];
int visit[300];
int dis[300];
int n,m,k;
int t;
void bfs(int x)
{
    visit[x]=1;
    dis[x]=0;
    queue<int>q;
    q.push(x);
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        if(top==t)
        {
            cout<<dis[t]+1<<endl;
            return ;
        }
        for(int i=1; i<=n; i++)
        {
            if(a[top][i]&&!visit[i])
            {
                visit[i]=1;
                dis[i]=dis[top]+1;
                q.push(i);
                //cout<<"i="<<i<<" "<<dis[i]<<endl;
            }
        }
    }
    cout<<"-1"<<endl;
}
int main()
{
    while(cin>>n>>m>>k)
    {
        memset(a,0,sizeof(a));
        for(int i=0; i<m; i++)
        {
            int u,v;
            int kk;
            cin>>u>>kk;
            while(kk--)
            {
                cin>>v;
                a[u][v]=1;
            }
        }
        while(k--)
        {
            memset(visit,0,sizeof(visit));
            memset(dis,0,sizeof(dis));
            cin>>t;
            bfs(1);
        }
    }
}

求大(dà)佬指點哪裏錯了(le/liǎo)。。。

#include <bits/stdc++.h>

using namespace std;
vector<int>v[500];
int dis[500];
int visit[501];
int t;
void bfs(int x)
{
    //cout<<t<<endl;
    visit[x]=1;
    dis[x]=1;
    queue<int>q;
    q.push(x);
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        //cout<<top<<endl;
        if(top==t)
        {
            //cout<<endl;
            cout<<dis[t]<<endl;
            return ;
        }
        for(int i=0; i<v[top].size(); i++)
        {
            if(!visit[v[top][i]])
            {
                visit[v[top][i]]=1;
                dis[v[top][i]]=dis[top]+1;
                //cout<<"i="<<v[top][i]<<" "<<dis[v[top][i]]<<endl;
                q.push(v[top][i]);
            }
        }
    }
    cout<<"-1"<<endl;
}
int main()
{
    int n,m,q;
    while(cin>>n>>m>>q)
    {
        for(int i=0; i<m; i++)
        {
            int k,kk;
            cin>>k>>kk;
            while(kk--)
            {
                int k2;
                cin>>k2;
                v[k].push_back(k2);
            }
        }
        while(q--)
        {
            memset(visit,0,sizeof(visit));//遍曆标記
            memset(dis,0,sizeof(dis));//距離記錄
            cin>>t;//要(yào / yāo)到(dào)的(de)點
            bfs(1);//從第一個(gè)點開始遍曆
        }
        v[500].clear();//清空
    }
    return 0;
}

相關案例查看更多