java实现The Settlers of Catan

The Settlers of Catan

题目

思路

因为要查找点之间的路径的最长长度，路过的点还有可能变为终点或者绕一个圈，之后再从这个点走向下一个点，所以我们不能标记点是否已走过，但是我们可以标记边已走过，因为边是不可以重复走的，因为是无向边，所以我们用二维数组标记边，当从一个点到另一个点时，我们就标记两端（例如，从A点已经走到了B点，我们就把A-B标记走过，B-A也标记走过，检查的时候就检查这个边的两端是否都没有走过），题目中说每个节点的度不超过三，那我们可以创建一个树，用左边、中间、右边来表示这个节点所连接的边，但是因为交的程序不能再定义一个类，所以我们应该想到使用内部类可以（因为以我目前的水平想不到更好的），以至于我使用了内部类来定义，但是因为刚开始不知道节点数量，不能定义很多的树，所以可以选择循环来创建，之后把创建的树用数组存起来（因为程序中不能留有很多的树的创建句），还有一个原因就是节点正好可以和数组下标对应，查找的时候直接输入数组下标就可以了。

代码

import java.util.*;public class Main {static TreeNode[] t;static boolean[][] vim;public static void main(String[] args) {Scanner in=new Scanner(System.in);Main m=new Main();   //创建主类对象，为了下面的内部类实例化int a=in.nextInt();int b=in.nextInt();//------------主程序-------------------------while(a!=0) {t=new TreeNode[a+5];for(int i=0;i<=a;i++) {      //创建每个节点TreeNode treei=m.new TreeNode(i);t[i]=treei;}int a1,a2;vim=new boolean[a+5][a+5];   //标记两个节点之间的路径//---------------因为是无向边，所以两边都要连接----------------------------------for(int i=0;i<b;i++) {a1=in.nextInt();a2=in.nextInt();if(t[a1].left==null) {t[a1].left=t[a2];t[a2].left=t[a1];}else if(t[a1].mid==null) {t[a1].mid=t[a2];t[a2].mid=t[a1];}else if(t[a1].right==null) {t[a1].right=t[a2];t[a2].right=t[a1];}}int max=0;//---------------查看每个节点所搜到的路径----------------------for(int i=0;i<t.length;i++) {int a8=dfs(t[i]);max=(a8>max)?a8:max;}System.out.println(max);a=in.nextInt();b=in.nextInt();}}//-------------------利用dfs搜索路径-------------------------------------------public static int dfs(TreeNode T) {if(T==null || (T.left==null && T.mid==null && T.right==null)) {return 0;}int min=0; //最长的路径//--------------------把两个点之间的之间的路径都标记，这样就不会出现重复的-----------------------------if(T.left!=null && vim[T.val][T.left.val]==false && vim[T.left.val][T.val]==false) {vim[T.val][T.left.val]=true;vim[T.left.val][T.val]=true;int a8=dfs(T.left)+1;vim[T.val][T.left.val]=false;vim[T.left.val][T.val]=false;min=(a8>min)?a8:min;}if(T.mid!=null && vim[T.val][T.mid.val]==false && vim[T.mid.val][T.val]==false) {vim[T.val][T.mid.val]=true;vim[T.mid.val][T.val]=true;int a8=dfs(T.mid)+1;vim[T.val][T.mid.val]=false;vim[T.mid.val][T.val]=false;min=(a8>min)?a8:min;}if(T.right!=null && vim[T.val][T.right.val]==false && vim[T.right.val][T.val]==false) {vim[T.val][T.right.val]=true;vim[T.right.val][T.val]=true;int a8=dfs(T.right)+1;vim[T.val][T.right.val]=false;vim[T.right.val][T.val]=false;min=(a8>min)?a8:min;}return min;}//-------------------内部类创建树-----------------------------class  TreeNode{int val;public TreeNode(int x) {val=x;}TreeNode left;TreeNode mid;TreeNode right;}
}