1. import java.util.*;
   
2. /**
   
3. * 10、 一位老农带着猫、狗、鱼过河，河边有一条船，
   
4.      每次老农只能带一只动物过河。
   
5.      当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，
   
6.      当老农和猫狗鱼在一起时，则不会发生这种问题。
   
7.      编程解决猫狗鱼过河问题。
   
8.      
   
9.      
   
10. * */
    
11. public class Test10 {
    
12.         //内部类，存放步骤
    
13.         private class Node {
    
14.                 int[] arr;
    
15.                 String mesg;
    
16.                 public void set(int[] arr, String mesg) {
    
17.                         this.arr = arr;
    
18.                         this.mesg = mesg;
    
19.                 }
    
20.                 public String toString() {
    
21.                         return Arrays.toString(arr) + "::" + mesg;
    
22.                 }
    
23.         }
    
24. //将步骤入队列
    
25.         private void set(int[] arr,String mesg){
    
26.            Node node=new Node();
    
27.            int[]  arrs=Arrays.copyOf(arr, arr.length);
    
28.            node.set(arrs, mesg);
    
29.            list.add(node);
    
30.     }
    
31.         //判断步骤是否安全
    
32.         //及判定  当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，
    
33.         private boolean isSafe(int arr[]){
    
34.                       if(arr[0]==0&&arr[1]==1&&(arr[2]==1||arr[3]==1))
    
35.                               return false;
    
36.                       return true;
    
37.          }
    
38.          //判定是否安全，每一步是否与队列中步骤有重复。     
    
39.         private boolean isVaid(int[] arr){
    
40.                     for (Iterator<Node> iterator = list.iterator(); iterator.hasNext();) {
    
41.                                 Node node = iterator.next();
    
42.                                 int [] arrs=node.arr;
    
43.                                         if(Arrays.equals(arr, arrs)){
    
44.                                                         return false;
    
45.                                         }
    
46.                                 }
    
47.                     return true;
    
48.          }
    
49.             //设置循环终点
    
50.         //当arr最中结果，全0
    
51.          private boolean isEnd(int [] arr){
    
52.                   int [] arrs=new int[arr.length];//int类型数组初始化为全0
    
53.                   //判断结果arr与arrs是否相等
    
54.                   if(Arrays.equals(arrs, arr)){
    
55.                           //如果相等表示循环条件不满足返回false
    
56.                           return false;
    
57.                   }
    
58.                   //如果不相等表示循环条件满足
    
59.                    return true;
    
60.            }
    
61.          //取反
    
62.          //当农夫不在起点时我们将要考虑河对岸的情况，就是将起点的每一个元素取反
    
63.            private int[]  reverse(int[] arr){
    
64.                    int [] arrSide = new int[arr.length];
    
65.                    for(int i=0;i<arr.length;i++){
    
66.                            if(arr[i]==1)
    
67.                                    arrSide[i]=0;
    
68.                            if(arr[i]==0)
    
69.                                    arrSide[i]=1;
    
70.                    }
    
71.                    return arrSide;
    
72.            }
    
73.            //移动元素
    
74.            /*
    
75.             * 农夫尝试带一个元素过河，
    
76.             * 判断这一步是否有效和安全，
    
77.             * 如果不安全或不有效
    
78.             * 就将这一步还原
    
79.             * 如此循环直到最终状态
    
80.             *
    
81.             * */
    
82.            public void remove(int [] arr){
    
83.                    String[] name={"","猫","狗","鱼"};//方便输出时的表
    
84.                    String [] flagStrs={"过河","回来"};
    
85.                    set(arr,"初始状态");//将初始状态入队列
    
86.                    int flag=0;
    
87.                    while(isEnd(arr)){
    
88.                           
    
89.                            if(arr[0]==1){//如果农夫在起点
    
90.                                   // 农夫尝试带一个元素过河
    
91.                                            for(int i=0;i<arr.length;i++){
    
92.                                                    //遇到元素不在这里跳过
    
93.                                                    if(arr[i]==0){
    
94.                                                            continue;
    
95.                                                    }
    
96.                                                    //
    
97.                                                    arr[0]=0;
    
98.                                                    arr[i]=0;
    
99.                                                    //i=0时表示考虑农夫是否是自己过河
    
100.                                                    if(i==0){
     
101.                                                            if(isSafe(arr)){
     
102.                                                                    if(flag==1){
     
103.                                                                            if(isVaid(reverse(arr))){
     
104.                                                                                    if(flag==1){
     
105.                                                                                            arr=reverse(arr);
     
106.                                                                                            set(arr, "农夫自己"+flagStrs[flag]);
     
107.                                                                                            flag=0;  
     
108.                                                                                            break;
     
109.                                                                                    }else if(flag==0){
     
110.                                                                                            set(arr, "农夫自己"+flagStrs[flag]);
     
111.                                                                                            flag=1;  
     
112.                                                                                            break;
     
113.                                                                                    }
     
114.                                                                            }
     
115.                                                                    }
     
116.                                                            }
     
117.                                                            }
     
118.                                                    //判断这一步是否有效如果无效就将状态归位，并跳过
     
119.                                                    if(!isSafe(arr)){
     
120.                                                           arr[0]=1;
     
121.                                                           arr[i]=1;
     
122.                                                            continue;
     
123.                                                    }
     
124.                                                    //判断农夫是否这一步是否安
     
125.                                                    //全如果安全就将这一步入队列
     
126.                                                    if(isVaid(arr)){
     
127.                                                            if(flag==1){
     
128.                                                                    arr=reverse(arr);
     
129.                                                                    set(arr,"农夫带着"+name[i]+flagStrs[flag]);
     
130.                                                                    flag=0;
     
131.                                                                    break;
     
132.                                                            }
     
133.                                                            if(flag==0){
     
134.                                                                       set(arr,"农夫带着"+name[i]+flagStrs[flag]);
     
135.                                                                       flag=1;
     
136.                                                                     break;
     
137.                                                            }
     
138.                                                    }else{
     
139.                                                           //不安全就将状态归位
     
140.                                                            arr[0]=1;
     
141.                                                            arr[i]=1;
     
142.                                                    }
     
143.                                            }
     
144.                            }else{
     
145.                                    //农夫不在起点时首先获取对岸情况
     
146.                                                    arr =reverse(arr);
     
147.                                             flag=1;
     
148.                                             continue;
     
149.                            }
     
150.                    }
     
151.            }
     
152.            public void print(){
     
153.                    remove(l);
     
154.                    for (Iterator<Node> iterator = list.iterator(); iterator.hasNext();) {
     
155.                         Node node =  iterator.next();
     
156.                         System.out.println(node);
     
157.                    }
     
158.                   
     
159.            }
     
160.            private int[] l={1,1,1,1};//数组的每个元素 l[0]农夫，l[1]猫, l[2]狗 ，l[3]鱼
     
161.          
     
162.        private ArrayList<Node> list=new ArrayList<Node>(); //步骤队列
     
163.                 public static void main(String[] args) {
     
164.                         Test10 t10=new Test10();
     
165.                         t10.print();
     
166.                 }
     
167.         }

复制代码

1. import java.util.*;
   
2. /**
   
3. * 10、 一位老农带着猫、狗、鱼过河，河边有一条船，
   
4.      每次老农只能带一只动物过河。
   
5.      当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，
   
6.      当老农和猫狗鱼在一起时，则不会发生这种问题。
   
7.      编程解决猫狗鱼过河问题。
   
8.      
   
9.      
   
10. * */
    
11. public class Test10 {
    
12.         //内部类，存放步骤
    
13.         private class Node {
    
14.                 int[] arr;
    
15.                 String mesg;
    
16.                 public void set(int[] arr, String mesg) {
    
17.                         this.arr = arr;
    
18.                         this.mesg = mesg;
    
19.                 }
    
20.                 public String toString() {
    
21.                         return Arrays.toString(arr) + "::" + mesg;
    
22.                 }
    
23.         }
    
24. //将步骤入队列
    
25.         private void set(int[] arr,String mesg){
    
26.            Node node=new Node();
    
27.            int[]  arrs=Arrays.copyOf(arr, arr.length);
    
28.            node.set(arrs, mesg);
    
29.            list.add(node);
    
30.     }
    
31.         //判断步骤是否安全
    
32.         //及判定  当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，
    
33.         private boolean isSafe(int arr[]){
    
34.                       if(arr[0]==0&&arr[1]==1&&(arr[2]==1||arr[3]==1))
    
35.                               return false;
    
36.                       return true;
    
37.          }
    
38.          //判定是否安全，每一步是否与队列中步骤有重复。     
    
39.         private boolean isVaid(int[] arr){
    
40.                     for (Iterator<Node> iterator = list.iterator(); iterator.hasNext();) {
    
41.                                 Node node = iterator.next();
    
42.                                 int [] arrs=node.arr;
    
43.                                         if(Arrays.equals(arr, arrs)){
    
44.                                                         return false;
    
45.                                         }
    
46.                                 }
    
47.                     return true;
    
48.          }
    
49.             //设置循环终点
    
50.         //当arr最中结果，全0
    
51.          private boolean isEnd(int [] arr){
    
52.                   int [] arrs=new int[arr.length];//int类型数组初始化为全0
    
53.                   //判断结果arr与arrs是否相等
    
54.                   if(Arrays.equals(arrs, arr)){
    
55.                           //如果相等表示循环条件不满足返回false
    
56.                           return false;
    
57.                   }
    
58.                   //如果不相等表示循环条件满足
    
59.                    return true;
    
60.            }
    
61.          //取反
    
62.          //当农夫不在起点时我们将要考虑河对岸的情况，就是将起点的每一个元素取反
    
63.            private int[]  reverse(int[] arr){
    
64.                    int [] arrSide = new int[arr.length];
    
65.                    for(int i=0;i<arr.length;i++){
    
66.                            if(arr[i]==1)
    
67.                                    arrSide[i]=0;
    
68.                            if(arr[i]==0)
    
69.                                    arrSide[i]=1;
    
70.                    }
    
71.                    return arrSide;
    
72.            }
    
73.            //移动元素
    
74.            /*
    
75.             * 农夫尝试带一个元素过河，
    
76.             * 判断这一步是否有效和安全，
    
77.             * 如果不安全或不有效
    
78.             * 就将这一步还原
    
79.             * 如此循环直到最终状态
    
80.             *
    
81.             * */
    
82.            public void remove(int [] arr){
    
83.                    String[] name={"","猫","狗","鱼"};//方便输出时的表
    
84.                    String [] flagStrs={"过河","回来"};
    
85.                    set(arr,"初始状态");//将初始状态入队列
    
86.                    int flag=0;
    
87.                    while(isEnd(arr)){
    
88.                           
    
89.                            if(arr[0]==1){//如果农夫在起点
    
90.                                   // 农夫尝试带一个元素过河
    
91.                                            for(int i=0;i<arr.length;i++){
    
92.                                                    //遇到元素不在这里跳过
    
93.                                                    if(arr[i]==0){
    
94.                                                            continue;
    
95.                                                    }
    
96.                                                    //
    
97.                                                    arr[0]=0;
    
98.                                                    arr[i]=0;
    
99.                                                    //i=0时表示考虑农夫是否是自己过河
    
100.                                                    if(i==0){
     
101.                                                            if(isSafe(arr)){
     
102.                                                                    if(flag==1){
     
103.                                                                            if(isVaid(reverse(arr))){
     
104.                                                                                    if(flag==1){
     
105.                                                                                            arr=reverse(arr);
     
106.                                                                                            set(arr, "农夫自己"+flagStrs[flag]);
     
107.                                                                                            flag=0;  
     
108.                                                                                            break;
     
109.                                                                                    }else if(flag==0){
     
110.                                                                                            set(arr, "农夫自己"+flagStrs[flag]);
     
111.                                                                                            flag=1;  
     
112.                                                                                            break;
     
113.                                                                                    }
     
114.                                                                            }
     
115.                                                                    }
     
116.                                                            }
     
117.                                                            }
     
118.                                                    //判断这一步是否有效如果无效就将状态归位，并跳过
     
119.                                                    if(!isSafe(arr)){
     
120.                                                           arr[0]=1;
     
121.                                                           arr[i]=1;
     
122.                                                            continue;
     
123.                                                    }
     
124.                                                    //判断农夫是否这一步是否安
     
125.                                                    //全如果安全就将这一步入队列
     
126.                                                    if(isVaid(arr)){
     
127.                                                            if(flag==1){
     
128.                                                                    arr=reverse(arr);
     
129.                                                                    set(arr,"农夫带着"+name[i]+flagStrs[flag]);
     
130.                                                                    flag=0;
     
131.                                                                    break;
     
132.                                                            }
     
133.                                                            if(flag==0){
     
134.                                                                       set(arr,"农夫带着"+name[i]+flagStrs[flag]);
     
135.                                                                       flag=1;
     
136.                                                                     break;
     
137.                                                            }
     
138.                                                    }else{
     
139.                                                           //不安全就将状态归位
     
140.                                                            arr[0]=1;
     
141.                                                            arr[i]=1;
     
142.                                                    }
     
143.                                            }
     
144.                            }else{
     
145.                                    //农夫不在起点时首先获取对岸情况
     
146.                                                    arr =reverse(arr);
     
147.                                             flag=1;
     
148.                                             continue;
     
149.                            }
     
150.                    }
     
151.            }
     
152.            public void print(){
     
153.                    remove(l);
     
154.                    for (Iterator<Node> iterator = list.iterator(); iterator.hasNext();) {
     
155.                         Node node =  iterator.next();
     
156.                         System.out.println(node);
     
157.                    }
     
158.                   
     
159.            }
     
160.            private int[] l={1,1,1,1};//数组的每个元素 l[0]农夫，l[1]猫, l[2]狗 ，l[3]鱼
     
161.          
     
162.        private ArrayList<Node> list=new ArrayList<Node>(); //步骤队列
     
163.                 public static void main(String[] args) {
     
164.                         Test10 t10=new Test10();
     
165.                         t10.print();
     
166.                 }
     
167.         }

复制代码