广度优先搜索练习之神奇的电梯

Love The Way You Lie 2022-07-12 13:00 128阅读 0赞

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  
Output

对于每次询问输出一个整数，占一行。代表如果要去某个楼层最少要经过多少层，如果到不了的话就输出-1。  
Example Input

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>
    #include<stdlib.h>
    char map[222][222];
    int visit[222];
    int jx[] = {
       1, 0, -1};
    int jy[] = {
       0, -1, -1};
    struct node
    {
        int x, y, c;
    }Q[2222], t, f;
    void bfs(int x, int n, int k)
    {
        int i, e = 0, s = 0;
        t.x = x;
        t.c = 0;
        visit[t.x]= 1;
        Q[e++] = t;
        while(s < e)
        {
            t = Q[s++];
            if(t.x == k)
            {
                printf("%d\n", t.c+1);
                return;
            }
            for(i = 1; i <= n; i++)
            {
                f.x = i;
                if(visit[f.x] == 0 && map[t.x][f.x])
                {
                    f.c = t.c + 1;
                    visit[f.x] = 1;
                    Q[e++] = f;
                }
            }
        }
        printf("-1\n");
    }
    int main()
    {
        int n, m, q, j;
        while(scanf("%d%d%d", &n, &m, &q) != EOF)
        {
            memset(map, 0, sizeof(map));
            int pos, num, i, k;
            for(i = 0; i < m; i++)
            {
                scanf("%d%d", &pos, &num);
                for(j = 0; j < num; j++)
                {
                    scanf("%d", &k);
                    map[pos][k] = 1;
                }
            }
            for(i = 0; i < q; i++)
            {
                memset(visit, 0, sizeof(visit));
                scanf("%d", &k);
                bfs(1, n, k);
            }
        }
        return 0;
    }