【PTA】L2-031 深入虎穴 (25分)

xsir 2020-06-28 PM 28℃ 0条 2389字 Site load time is:7 ms 百度:已收录

原题地址:L2-031 深入虎穴 (25分)

著名的王牌间谍 007 需要执行一次任务,获取敌方的机密情报。已知情报藏在一个地下迷宫里,迷宫只有一个入口,里面有很多条通路,每条路通向一扇门。每一扇门背后或者是一个房间,或者又有很多条路,同样是每条路通向一扇门…… 他的手里有一张表格,是其他间谍帮他收集到的情报,他们记下了每扇门的编号,以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。

内线告诉他,情报就藏在迷宫的最深处。但是这个迷宫太大了,他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。

输入格式:
输入首先在一行中给出正整数 N(<10^5​),是门的数量。最后 N 行,第 i 行(1≤i≤N)按以下格式描述编号为 i 的那扇门背后能通向的门:

K D[1] D[2] ... D[K]

其中 K 是通道的数量,其后是每扇门的编号。

输出格式:
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。

输入样例:

13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0

输出样例:

12

思路:
根据题目的意思,不难看出整个迷宫就是一棵树,迷宫入口就是树的根节点,每一扇门
就是树上的节点,题目要求的找出距离入口最远的那扇门意思就是:找出距离根节点最远的节点(深度最深的节点)。既然这样的话,我们就可以从根节点开始遍历,遍历到叶子节点的时候,判断一下当前节点的深度是否大于最深深度(事先定义好),是的话就更新最深深度为当前节点的深度和最深深度对应的节点编号为当前节点编号,否则不做处理。

代码:


/**
 * 思路: 
 * 1、确定存储结构:指针数组 + 一维数组                     
 * 2、找出根节点
 * 3、从根节点开始遍历,遍历过程中维护最长路径及对应叶子节点编号
 * 4、输出最远叶子节点编号 
 */

 

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define N 100005

// 定义指针数组 
int* list[N] = { NULL };
// 用来找出根节点 
int root[N] = { 0 };


/**
 * @param rt    当前节点的编号 
 * @param d    当前节点的深度 
 */
void traverse(int rt, int d) {
    // 获取rt节点下的子节点个数 
    int len = list[rt][0];
    
    // 达到叶子节点 
    if(len == 0) {
        if(d > list[0][0]) {
            list[0][0] = d;
            list[0][1] = rt;
        } 
        return;
    } 
    
    // 遍历rt的所有子节点 
    for(int j = 1; j <= len; ++j) {
        traverse(list[rt][j], d + 1);
    }    
}


int main() {
    freopen("C://Users/user/Desktop/a.txt", "r", stdin);
                         
    int n, k, rt = 0;
    scanf("%d", &n);
    
    // list[0]指向的数组第0位用来存储深度和叶子节点编号
    list[0] = (int*)malloc(sizeof(int) * 2);
    list[0][0] = -1; 
    list[0][1] = -1;  
    
    // 1、存储数据 
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &k);
        
        list[i] = (int*)malloc(sizeof(int) * (k + 1));
        
        // list[i]指向的数组第0位记录数组个数 
        list[i][0] = k;
        
        for(int j = 1; j <= k; ++j) {
            scanf("%d", &list[i][j]);
            root[list[i][j]] = 1; 
        } 
        
    
    } 
    
    // 2、找根节点 
    for(int i = 1; i <= n; ++i) {
        if(!root[i]) {
            rt = i;
            break;
        }
    }
    
    // 3、遍历 
    traverse(rt, 0);
        
    // 4、输出结果 
    printf("%d\n", list[0][1]); 
    
    // 5、释放内存 
    for(int i = 1; i <= n; ++i) {
        free(list[i]);
    } 
    
    return 0;
标签: none

非特殊说明,本博所有文章均为博主原创。

上一篇 maven项目打包
下一篇 没有了

评论啦~


召唤看板娘