hdu1181变形课dfs/bfs/并查集三种解法(java)
【摘要】 题目链接 Problem Description
呃…变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体. Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能...
题目链接
Problem Description
呃…变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.
Input
测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.
Output
如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)
Sample Input
so
soon
river
goes
them
got
moon
begin
big
0
Sample Output
Yes.
Hint
Hint
Harry 可以念这个咒语:“big-got-them”.
首先这是一题水题。但是题目比较灵活，解题思路较多，温习下各种算法的实现。
并查集：
- 这题因为是查找最终的关系，所以可以用并查集来处理对象的关系，进行查找合并，最终查看b点是否为m点的父亲。这合并的过程要注意不能压缩路径，并且m点不做父节点。因为m是根节点防止m成为父节点造成关系混乱。
dfs：
- 可以用list[]数组作为灵界表储存各个节点信息，因为节点都是’a’-'z’的节点，所以可以直接深搜。
bfs：
- 这题bfs也可以，用队列添加m(12)，从m点开始遍历找到’b’点，输出结果。
注意点：
输入多组数据，不仅仅是一项到0多组数据，到0输出后还有初始化参数完成下一轮，也就是这题理论是没有输入结束状态的！wa了好久因为这个。
并查集：
import java.util.Scanner;
public class 杭电1181并查集 {
static int a[];//储藏父节点
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner sc=new Scanner(System.in);
init();
while(sc.hasNext())
{ String str=sc.next(); if(str.equals("0")) { int index=a[12]; if(a[12]==-1) {System.out.println("No.");}//m这个点没有父亲 else { int value=search(12); if(value==1) {System.out.println("Yes.");} else System.out.println("No."); } init(); } else { int start=str.charAt(0)-'a'; int end=str.charAt(str.length()-1)-'a'; join(start, end); }
}
}
static void init() {
a=new int[26];
for(int i=0;i<26;i )
{ a[i]=-1;
}
}
static int search(int i)//查找父节点编号
{
if(a[i]==-1)return i;
else return search(a[i]);
}
static void join(int b1,int b2)//b1<-b2 b1为父亲
{
int a1=search(b1);//b1父节点
int a2=search(b2);//b2 父节点
if(a1==a2) {}//已经在一棵树上
else if(a1==12) {}//m点不做任何点的父节点，他是最底层的根节点
else if(a2==1){}//b不做儿子，只做父亲，不然m点最上父节点可能是b爸爸
else { a[a2]=a1;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
dfs:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class 杭电1181dfs {
static boolean judgle=false;
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner sc=new Scanner(System.in);
Listlist[]=new ArrayList[26];
for(int i=0;i<26;i )
{ list[i]=new ArrayList<>();
}
boolean jud[]=new boolean[26];
while(sc.hasNext())
{ String str=sc.nextLine(); if(str.equals("0")) { dfs(list,1,jud); if(judgle) {System.out.println("Yes.");} else System.out.println("No."); //初始化参数 judgle=false; jud=new boolean[26]; for(int i=0;i<26;i ) { list[i]=new ArrayList<>(); } } else { char font=str.charAt(0); char end=str.charAt(str.length()-1); if(font!=end) list[(int)(font-'a')].add((int)(end-'a')); }
}
}
private static void dfs(List[] list, int i, boolean[] jud) {
// TODO 自动生成的方法存根
if(i==12) {judgle=true;}
if(!judgle)
{ for(int j=0;j>map=new HashMap<>();
while(sc.hasNext())
{ String s=sc.nextLine(); if(s.equals("0")) { Queue q1=new ArrayDeque<>(); if(!map.containsKey("b")) {System.out.println("No.");} else { Set jud=new HashSet<>(); q1.add("b");jud.add("b"); boolean j=false; while(!q1.isEmpty()) { String node=q1.poll(); if(node.equals("m")) { System.out.println("Yes."); j=true; break; } else { if(map.containsKey(node)) { Set set2=map.get(node); for(String team:set2) { if(jud.contains(team)) {continue;} else { jud.add(team); q1.add(team); } } } } } if(!j) {System.out.println("No.");} } map.clear(); } String start=s.substring(0, 1); String end=s.substring(s.length()-1); if(map.containsKey(start)) {Set set2=map.get(start);set2.add(end); map.put(start, set2);} else { Set set=new HashSet<>(); set.add(end);map.put(start, set); }
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
list套数组法：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class 杭电11811 {
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner sc=new Scanner(System.in);
Listlist[]=new ArrayList[26];
for(int i=0;i<26;i )
{ list[i]=new ArrayList<>();
}
boolean jud[]=new boolean[26];
while(sc.hasNext())
{ String str=sc.nextLine(); if(str.equals("0"))//b m 1 11 { Queueq1=new ArrayDeque<>(); q1.add(1); jud[1]=true; boolean bool=false; while(!q1.isEmpty()) { int team=q1.poll(); if(team==12) {System.out.println("Yes.");bool=true;break;} else { for(int j=0;j(); } jud=new boolean[26]; } else { char font=str.charAt(0); char end=str.charAt(str.length()-1); if(font!=end) list[(int)(font-'a')].add((int)(end-'a')); }
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
水平有限，如果有错，还请大佬指正。
- 如果对
后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai
文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。
原文链接：bigsai.blog.csdn.net/article/details/88671419
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）