廣度優先搜索練習之神奇的電梯
Time Limit: 1000ms Memory limit: 65536K
題目描述
有一座已知層數為n的高樓，這座高樓的特殊之處在于只能靠電梯去上下樓，所以要去到某一層要非常耽誤時間，然而更悲哀的是，這座高樓的電梯是限號的，小鑫最開始的時候在1層，他想去第x層，問題是他最起碼要經過多少層(包含第x層)才能到達第x層。
輸入
多組輸入。
第一行是三個正整數n,m,q。分別代表樓的總層數，給定的m條信息和q次查詢。
接下來的m行，每行的第一個整數pos代表這是第pos層的電梯，第二個數代表從這一層可以去的樓層總共有num個，之后的num個數字代表從第pos層代表可以去的樓層。
最后的q行，每行一個整數代表小鑫想去的樓層號碼。
1<=m,pos,num<=n<=200
1<=q<=20
輸出
對于每次詢問輸出一個整數，占一行。代表如果要去某個樓層最少要經過多少層，如果到不了的話就輸出-1。
示例輸入
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
示例輸出
5
3
-1
題目方法：bfs+鄰接矩陣，隊列的基本操作
前提準備：
#include<queue>詳細用法:
定義一個queue的變量 queue M
查看是否為空范例 M.empty() 是的話返回1，不是返回0;
從已有元素后面增加元素 M.push()
輸出現有元素的個數 M.size()
顯示第一個元素 M.front()
顯示最后一個元素 M.back()
清除第一個元素 M.pop()
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <queue>
using namespace std;
int k,key,h;
int map1[2000][2000];
int vir[2000];
struct node
{int x;int y;int time;
};
void bfs(int x)
{node t,f;queue<node> Q;t.x=x;t.time=0;Q.push(t);vir[x]=1;while(!Q.empty()){t=Q.front();Q.pop();if(t.x==key){printf("%d\n",t.time+1);return;}for(int i=1;i<=k;i++){f.x=i;if(vir[f.x]==0&&map1[t.x][f.x]){f.time = t.time+1;vir[f.x]=1;Q.push(f);}}}printf("-1\n");return ;
}
int main()
{int a,i,m,b;while(~scanf("%d%d%d",&k,&m,&h)){memset(map1,0,sizeof(map1));for(i=0;i<m;i++){scanf("%d%d",&a,&b);for(int j=0;j<b;j++){int h1;scanf("%d",&h1);map1[a][h1]=1;}}for(i=1;i<=10;i++){for(int j=1;j<=10;j++){printf("%d",map1[i][j]);}printf("\n");}for(i=0;i<h;i++){memset(vir,0,sizeof(vir));scanf("%d",&key);bfs(1);}}return 0;
}
