解题思路
暴搜
由于实在太菜了,只能想到暴搜。各位看官全当看个笑话罢
由于第一个单词为出现过的牛,最后一个为之前出现过的牛
因此可以构建出一个以牛 Bessie
为根节点,子节点为数组(存储牛)的二叉树
1. 左子树表示之前 previous
2. 右子树表示之后 next
二叉树构建完成后就可以进行深度搜索树了,从 Bessie
开始进行搜索
当遇到 牛Elsie
时结束搜索,并将答案储存
Java代码如下
import java.util.*;
public class Main{
static List<String> year =new ArrayList<String>(){{
add("Ox");
add("Tiger");
add("Rabbit");
add("Dragon");
add("Snake");
add("Horse");
add("Goat");
add("Monkey");
add("Rooster");
add("Dog");
add("Pig");
add("Rat");
}};//十二生肖
static int ans = -1;
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
scan.nextLine();
Node root = new Node("Bessie","Ox");//根节点为牛Bessie
//构建树
for(int i = 0;i<N;i++){
String[] temp = scan.nextLine().split(" ");
if("next".equals(temp[3])) {
insert(root,temp[7],new Node(temp[0],temp[4]),true);
}else {
insert(root,temp[7],new Node(temp[0],temp[4]),false);
}
}
dfs(root,0);
System.out.println(ans);
scan.close();
}
public static void dfs(Node node,int count){
//找到牛Elsie,储存结果并返回
if("Elsie".equals(node.cow)){
ans =(int) Math.abs(count);
return ;
}
int nodeYearIndex = year.indexOf(node.cowYear);
List<Node> list1 = node.left;
for(int i = 0;i<list1.size();i++){
Node temp = list1.get(i);
int tempYearIndex = year.indexOf(temp.cowYear);
int count1 = nodeYearIndex-tempYearIndex;
if(count1<=0){
dfs(temp,count-(12+count1));
}
else{
dfs(temp,count-count1);
}
}
List<Node> list2 = node.right;
for(int i = 0;i<list2.size();i++){
Node temp = list2.get(i);
int tempYearIndex = year.indexOf(temp.cowYear);
int count1 = tempYearIndex-nodeYearIndex;
if(count1<=0){
dfs(temp,count+12+count1);
}
else{
dfs(temp,count+count1);
}
}
}
public static void insert(Node root,String cow1,Node node,boolean flag){
Node temp = null;
if(cow1.equals(root.cow))
temp = root;
else
temp = find(root,cow1);
if(flag){
temp.right.add(node);
}
else{
temp.left.add(node);
}
}
public static Node find(Node root,String target){
Node result = null;
List<Node> left = root.left;
Node temp1 = null;
for(int i = 0;i<left.size();i++){
Node temp = left.get(i);
if(target.equals(temp.cow))
return temp;
temp1 = find(temp,target);
result = temp1==null?result:temp1;
}
Node temp2 = null;
List<Node> right = root.right;
for(int i = 0;i<right.size();i++){
Node temp = right.get(i);
if(target.equals(temp.cow))
return temp;
temp2 = find(temp,target);
result = temp2==null?result:temp2;
}
return result;
}
}
class Node{
String cow;
String cowYear;
List<Node> left;
List<Node> right;
public Node(String cow,String cowYear){
this.cow = cow;
this.cowYear = cowYear;
left = new ArrayList<>();
right = new ArrayList<>();
}
}
你来搞开发的吗