首页 > 代码库 > timus 1242. Werewolf【队列+结构体】
timus 1242. Werewolf【队列+结构体】
题目链接http://acm.timus.ru/problem.aspx?space=1&num=1242
大致题意:村庄里有几个人不幸被害,是狼人干的!(插一句,这里可以想到一部电影《狼人》,很惊悚),现在就是需要找出可能是狼人的村民!
已知狼人不会去杀自己的祖宗,也不会杀自己的后代。狼人的父母不超过2个人!(儿女?这个不清楚)。
这里给出村里人数n(编号1~n),
给出关系a b
其中a是b的子(女),b是a的父(母)
也给出被害村民的编号。
递增输出可能是狼人的村民的编号,如果没有则输出0
这里的输入有点不按常理,既有字符串的输入,也有数字输入,这个需要判断!
还有被害人数没有给,这个也需要字符判断!
只说思路,因为每个子女人数不确定,就用队列来维护村民子女的编号
#include<queue>
queue<int> vil[1005];
用结构体存储村民父母的编号
struct Vil
{
int parent1,parent2;
};
Vil v[1005];
根据被害村民,对其直系关系的村民进行递归(dfs)排除其嫌疑即可!
这里使用队列主要出于减少空间考虑的,也可以写在一个结构体里,给子女那块分配相应的空间!
总的思路就是这样了!
timus 1242. Werewolf【队列+结构体】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。