广度优先搜索练习之神奇的电梯
Time Limit: 1000MS
Memory Limit: 65536KB
Problem Description
有一座已知层数为n的高楼,这座高楼的特殊之处在于只能靠电梯去上下楼,所以要去到某一层要非常耽误时间,然而更悲哀的是,这座高楼的电梯是限号的,小鑫最开始的时候在1层,他想去第x层,问题是他最起码要经过多少层(包含第x层)才能到达第x层。
Input
多组输入。
第一行是三个正整数n,m,q。分别代表楼的总层数,给定的m条信息和q次查询。
接下来的m行,每行的第一个整数pos代表这是第pos层的电梯,第二个数代表从这一层可以去的楼层总共有num个,之后的num个数字代表从第pos层代表可以去的楼层。
最后的q行,每行一个整数代表小鑫想去的楼层号码。
1<=m,pos,num<=n<=200
1<=q<=20
第一行是三个正整数n,m,q。分别代表楼的总层数,给定的m条信息和q次查询。
接下来的m行,每行的第一个整数pos代表这是第pos层的电梯,第二个数代表从这一层可以去的楼层总共有num个,之后的num个数字代表从第pos层代表可以去的楼层。
最后的q行,每行一个整数代表小鑫想去的楼层号码。
1<=m,pos,num<=n<=200
1<=q<=20
Output
对于每次询问输出一个整数,占一行。代表如果要去某个楼层最少要经过多少层,如果到不了的话就输出-1。
Example 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
Example Output
5 3 -1
Hint
Author
Casithy
#include <stdio.h>
#include <string.h>
struct node
{int x;int size;
}link[204], t, f;
int tp, op, n;
int map[204][204], vis[204];
void BFS(int x1, int X)
{memset(vis, 0, sizeof(vis));memset(link, 0, sizeof(link));tp = op = 0;t.x = 1;t.size = 0;link[tp++] = t;vis[t.x] = 1;while(op < tp){f = link[op++];if(f.x == X){printf("%d\n", f.size + 1);return;}for(int i = 1; i <= n; i++){if(map[f.x][i] == 1 && vis[i] == 0){t.x = i;t.size = f.size + 1;link[tp++] = t;vis[i] = 1;}}}printf("-1\n");
}
int main()
{int m, q, u, num, v, X;while(scanf("%d %d %d", &n, &m, &q) != EOF){memset(map, 0, sizeof(map));while(m--){scanf("%d", &u);scanf("%d", &num);while(num--){scanf("%d", &v);map[u][v] = 1;}}while(q--){scanf("%d", &X);BFS(1, X);}}return 0;
}