前言

這個問題的拋出，是幾個星期之前的算法課程偿曙。老師分析了半天，最后的結(jié)論是：其實就是圖的遍歷羔巢。那時候挺懵逼的望忆，不管是對于圖，還是遍歷竿秆，或者是數(shù)據(jù)結(jié)構(gòu)启摄，心里面都沒有一個十足的概念，所以擱置了這么久的問題幽钢，現(xiàn)在就來好好研究清楚歉备。

問題描述：

一個農(nóng)夫在河邊要過河，但是他帶著一匹狼匪燕、一只羊和一顆白菜蕾羊。他需要用船將這三樣?xùn)|西運至對岸喧笔，然而，這艘船的空間有限龟再，只容得下他自己和另一樣?xùn)|西（或狼或羊或白菜）书闸。若他不在場看管的話，狼就會吃羊利凑，羊就會去吃白菜浆劲。此人如何才能過河。

問題分析：

拋開算法哀澈，把這個題當成是一個簡單的邏輯題的話還是挺好解的牌借，你過不了多久你就會發(fā)現(xiàn)幾個關(guān)鍵的問題：

• 1.你要時刻注意農(nóng)夫的位置，因為農(nóng)夫不在地時候狼會吃羊割按，羊會吃菜
• 2.第一步只能把羊帶走
• 3.最后一步只能是把羊從河對岸帶過來

你會發(fā)現(xiàn)羊其實是問題的關(guān)鍵膨报，只要保證羊和狼和白菜隔離開來，那么就很容易解這個問題哲虾。下面是這道題的答案：

①把羊帶到河對岸 -> 把狼帶到河對岸丙躏，再把羊帶回來 -> 把白菜帶到河對岸 -> 把羊帶到河對岸
②把羊帶到河對岸 -> 把白菜帶到河對岸，再把羊帶回來 -> 把狼帶到河對岸 -> 把羊帶到河對岸

算法分析：

過河問題束凑，其實質(zhì)就是一種狀態(tài)的改變晒旅，就像這個問題說的，農(nóng)夫狼羊菜都要從河的這邊到對岸去汪诉，也就對應(yīng)了兩個狀態(tài)废恋，一個是沒過河的狀態(tài)，一個是過了河的狀態(tài)扒寄。

狀態(tài)的改變

所以很自然的聯(lián)想到了用0和1來表示他們的狀態(tài)鱼鼓，并且每時每刻，農(nóng)夫狼羊菜的狀態(tài)都對應(yīng)一個特定的狀態(tài)该编，比如沒過河的狀態(tài)是0000迄本，四個都沒有過河，而過河的狀態(tài)是1111课竣。這樣做的好處是將問題抽象成了計算機能夠處理的數(shù)據(jù)嘉赎。

你當然可以選擇暴力窮舉法，列出所有可能并找出合理的于樟，這是屢試不爽而且行之有效（對于自己來說）的方法公条。

但這并不是聰明的做法。如果學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)得好的同學(xué)（不包括我）迂曲，會想到用圖的V來描述每一種狀態(tài)靶橱，用E來描述狀態(tài)之間的對應(yīng)關(guān)系，最后進行圖的遍歷就能找到答案了。反正當時我是想不到的..

圖形簡單回顧

圖是一種很重要的數(shù)據(jù)結(jié)構(gòu)关霸，這里就簡單用相鄰矩陣表示法來簡單回顧并描述一下圖吧传黄。

1.下圖是一個無向圖，有五個頂點谒拴，所以我們使用5x5的數(shù)組存放圖形尝江。

無向圖

2.在上圖中，先找和①相鄰的頂點有哪些英上，把和①相鄰的頂點2和頂點5的坐標填入1：

找和①相鄰的頂點

3.其他頂點以此類推可以得到相鄰矩陣：

相鄰矩陣

至此我們就利用一個二維數(shù)組來描述了一個圖形炭序，0表示沒有邊連接，1表示有邊苍日。

繼續(xù)分析問題

上面提到可以用0,1來表示某一時刻特定的狀態(tài)惭聂，很簡單的分析可以得到只存在以下10種情況（右邊表示河對岸）：

農(nóng)夫狼羊菜 | （空）
農(nóng)夫羊菜 | 狼_________農(nóng)夫狼菜 | 羊_________農(nóng)夫狼羊 | 菜
狼菜 | 農(nóng)夫羊_________農(nóng)夫羊 | 狼菜
狼 | 農(nóng)夫羊菜_________羊 | 農(nóng)夫狼菜_________菜 | 農(nóng)夫狼羊
（空） | 農(nóng)夫狼羊菜

所以抽象成01可以這樣表示：

0000
0100_________0010_________0001
1010_________0101
1011_________1101_________1110
1111

這樣就得到了我們的頂點集合，這些頂點包含了各個對象的狀態(tài)相恃，所以我們需要創(chuàng)建一個Vertex類來表示頂點辜纲，里面或許會要再需要一個ObjState類來描述對象各自的狀態(tài)。然后我們需要一個二維數(shù)組來表示相鄰矩陣拦耐。

再思考

思考：我們現(xiàn)在有了：

• 一個頂點類耕腾，里面包含了描述各個對象狀態(tài)的ObjState類。
• 一個用來描述邊集的空的二維數(shù)組（里面還沒有數(shù)據(jù)）

我們程序的最終目的杀糯，是要找到過河的方案扫俺，至少得要輸出整個過程吧，因為Vertex本身描述的就是一個特定的狀態(tài)固翰，所以可以加入一個String類型的字符串來描述這樣的狀態(tài)狼纬，例如：0000描述為“最開始的狀態(tài)"，0100描述為”農(nóng)夫羊菜 | 狼“骂际。

頂點連通的條件

我們有了這樣的一些擁有自身狀態(tài)信息的頂點疗琉，還需要判斷他們的連通性，也就是找“邊”歉铝。仔細思考一下你就會發(fā)現(xiàn)盈简，其實兩個狀態(tài)的連通就只有兩個條件：

1.man的狀態(tài)不一樣：
這是因為要保證完成過河的動作，因為過河的這個動作保證了行動的進行太示，只有過河才能改變現(xiàn)在的狀態(tài)到下一個狀態(tài)柠贤，這是過程進行的必然條件。
2.最多只有一個其他對象的狀態(tài)不一樣：
除了保證man的狀態(tài)不一樣先匪，也要保證狼羊菜這三個對象中，最多只有1個對象的狀態(tài)不一樣弃衍。

所以我們只要判斷兩兩點之間呀非，是否滿足以上狀態(tài)，如果滿足，則把相鄰矩陣的對應(yīng)位置置為1即可岸裙。

遍歷圖的條件

我們現(xiàn)在有了描述頂點的Vertex類猖败，有了一個表示邊集的二維數(shù)組，那么就要遍歷圖來尋找滿足條件的路徑了降允。

我們需要注意的是恩闻，如何防止路徑的重復(fù)查找，也就是在一條路上走來走去的情況剧董，我們需要引入一個額外的描述當前點是否訪問過的一維數(shù)組visited[]幢尚，默認的值應(yīng)該小于等于0，如果該點訪問了翅楼，則把對應(yīng)的visited置為訪問該點的點的編號尉剩，例如點2訪問點5，那么visited[4] = 2毅臊，這樣做的好處是理茎，輸出的時候就能很方便的遍歷出相應(yīng)的路徑。

要多多分析問題

多多分析問題管嬉，更能幫助我們分析清楚問題皂林，也能幫助我們找到比較好的編程實現(xiàn)方法，會少走許多彎路蚯撩，總之就是要多多分析問題础倍，對于編程來說，這是比磨刀不誤砍柴工還要高上幾個級別的事求厕。

總之就是要多分析問題著隆，再開始寫代碼。

寫代碼：

ObjState類：

首先創(chuàng)建一個描述對象屬性的類：

class ObjState{
    // 對象類呀癣，保存了對象的狀態(tài)
    public int man;
    public int wolf ;
    public int sheep;
    public int vegetable;
}

其中定義了int類型的四種對象（其實就是四個變量美浦，來簡單模擬四個對象）。
初始化的工作可以交給Vertex類：

Vertex類：

頂點類项栏，包含了ObjState類浦辨，保存了頂點對象的狀態(tài)以及輸出時的信息。

class Vertex {
    ObjState objState = new ObjState();     // 對象狀態(tài)信息
    String outputMessage;                   // 輸出時要顯示的信息
    public Vertex(int manState, int wolfState, int sheepState,
                  int vegetableState, String outputMessage){
        // 初始化工作
        objState.man = manState;
        objState.wolf = wolfState;
        objState.sheep = sheepState;
        objState.vegetable = vegetableState;
        this.outputMessage = outputMessage;
    }
}

Tester主類：

1.首先在main函數(shù)外邊定義三個全局變量：

public static int[][] arr = new int[10][10];    // 保存了相鄰矩陣信息
public static ArrayList<Vertex> arrayList = new ArrayList<>();  // 頂點集
public static int[] visited = new int[10];      // 用來保存是否遍歷

2.然后在main函數(shù)中添加進我們的是個頂點：

arrayList.add(new Vertex(0, 0, 0, 0, "初始狀態(tài)"));
arrayList.add(new Vertex(0, 1, 0, 0, "農(nóng)夫羊菜 | 狼"));
arrayList.add(new Vertex(0, 0, 1, 0, "農(nóng)夫狼菜 | 羊"));
arrayList.add(new Vertex(0, 0, 0, 1, "農(nóng)夫狼羊 | 菜"));
arrayList.add(new Vertex(1, 0, 1, 0, "狼菜 | 農(nóng)夫羊"));
arrayList.add(new Vertex(0, 1, 0, 1, "農(nóng)夫羊 | 狼菜"));
arrayList.add(new Vertex(1, 0, 1, 1, "狼 | 農(nóng)夫羊菜"));
arrayList.add(new Vertex(1, 1, 0, 1, "羊 | 農(nóng)夫狼菜"));
arrayList.add(new Vertex(1, 1, 1, 0, "菜 | 農(nóng)夫狼羊"));
arrayList.add(new Vertex(1, 1, 1, 1, "已經(jīng)全部過河"));

3.初始化我們的相鄰矩陣數(shù)組：

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
        arr[i][j] = 0;
    }
}   // for循環(huán)結(jié)束初始化數(shù)組

4.找邊：
因為我們定義的狀態(tài)為int類型沼沈，所以判斷第二個條件時流酬，需要加上絕對值，看不懂多看兩邊就看懂了列另。

for (int i = 0; i < 10; i++) {
   // 滿足兩個條件：①man的狀態(tài)不一樣②有且僅有最多一個狼羊菜中的一個對象狀態(tài)不一樣    int temp_i_Man = arrayList.get(i).objState.man;
    int temp_i_Wolf = arrayList.get(i).objState.wolf;
    int temp_i_Sheep = arrayList.get(i).objState.sheep;
    int temp_i_Vegetable = arrayList.get(i).objState.vegetable;
    for (int j = 0; j < 10; j++) {
        int temp_j_Man = arrayList.get(j).objState.man;
        int temp_j_Wolf = arrayList.get(j).objState.wolf;
        int temp_j_Sheep = arrayList.get(j).objState.sheep;
        int temp_j_Vegetable = arrayList.get(j).objState.vegetable;
        if (temp_i_Man != temp_j_Man && (Math.abs(temp_i_Wolf - temp_j_Wolf) +
                        Math.abs(temp_i_Sheep - temp_j_Sheep) +
                        Math.abs(temp_i_Vegetable - temp_j_Vegetable) <= 1)) {
            arr[i][j] = 1;          // 滿足以上條件則滿足連通性芽腾，置為1
        }
    }
}

5.可以試著輸出相鄰矩陣：

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
        System.out.printf("%2d", arr[i][j]);
    }
    System.out.println();   // 換行操作
}

編寫dfs方法來遍歷圖：

記得在調(diào)用這個方法之前要把visited[0]置為1，因為我們使從第一個點出發(fā)的页衙。

public static void dfs(int start, int end) {
    if (start == end) {
        print(end);    // 調(diào)用print()方法輸出結(jié)果
        System.out.println();
    }

    for (int i = 0; i < 10; i++) {
        if (arr[start-1][i] > 0 && visited[i] == 0) {
            // 有邊且沒有被訪問
            visited[i] = start;
            dfs(i+1, end);
            visited[i] = 0; // 回溯時置為0
        }
    }
}

編寫print類來輸出結(jié)果：

public static void print(int end) {
    // 從最后往前遍歷摊滔，然后正序輸出
    int[] temp = new int[10]; // 保存了倒敘輸出的順序
    int num = 0;    // num表示要輸出的個數(shù)
    int i = end;    // i表示當前是第幾個數(shù)
    while (i != 1) {
        // 當i不是第一個數(shù)字時阴绢，則繼續(xù)往前找
        temp[num] = visited[i - 1];
        i = temp[num];
        num++;      // num加1
    }
    for (int j = num - 1; j > 0; j--) {
        System.out.println(arrayList.get(temp[j] - 1).outputMessage);
    }
    // 輸出最終狀態(tài)
    System.out.println(arrayList.get(9).outputMessage);
}

最后的結(jié)果：

0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0
0 0 0 0 1 0 1 0 1 0
0 0 0 0 0 0 1 1 0 0
1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 1
0 0 1 1 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
初始狀態(tài)
狼菜 | 農(nóng)夫羊
農(nóng)夫狼菜 | 羊
狼 | 農(nóng)夫羊菜
農(nóng)夫狼羊 | 菜
羊 | 農(nóng)夫狼菜
已經(jīng)全部過河

初始狀態(tài)
狼菜 | 農(nóng)夫羊
農(nóng)夫狼菜 | 羊
菜 | 農(nóng)夫狼羊
農(nóng)夫羊菜 | 狼
羊 | 農(nóng)夫狼菜
已經(jīng)全部過河

完整的程序：

package wudi.lt;

import java.util.ArrayList;

/**
 * ★狼羊菜問題詳細學(xué)習(xí)
 * 歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處：
 * 簡書地址：http://www.reibang.com/u/a40d61a49221
 * CSDN地址：http://blog.csdn.net/qq939419061
 *
 * ★如果有任何的問題艰躺，歡迎給我留言呻袭，本程序只供學(xué)習(xí)使用，謝謝腺兴！
 *
 * @author:我沒有三顆心臟
 * @create:2017-09-25-15:25
 */
class ObjState{
    // 對象類左电，保存了對象的狀態(tài)
    public int man;
    public int wolf ;
    public int sheep;
    public int vegetable;
}
class Vertex {
    ObjState objState = new ObjState();     // 對象狀態(tài)信息
    String outputMessage;                   // 輸出時要顯示的信息
    public Vertex(int manState, int wolfState, int sheepState,
                  int vegetableState, String outputMessage){
        // 初始化工作
        objState.man = manState;
        objState.wolf = wolfState;
        objState.sheep = sheepState;
        objState.vegetable = vegetableState;
        this.outputMessage = outputMessage;
    }
}

public class Tester1 {
    public static int[][] arr = new int[10][10];    // 保存了相鄰矩陣信息
    public static ArrayList<Vertex> arrayList = new ArrayList<>();  // 頂點集
    public static int[] visited = new int[10];      // 用來保存是否遍歷

    public static void main(String[] args) {
        arrayList.add(new Vertex(0, 0, 0, 0, "初始狀態(tài)"));
        arrayList.add(new Vertex(0, 1, 0, 0, "農(nóng)夫羊菜 | 狼"));
        arrayList.add(new Vertex(0, 0, 1, 0, "農(nóng)夫狼菜 | 羊"));
        arrayList.add(new Vertex(0, 0, 0, 1, "農(nóng)夫狼羊 | 菜"));
        arrayList.add(new Vertex(1, 0, 1, 0, "狼菜 | 農(nóng)夫羊"));
        arrayList.add(new Vertex(0, 1, 0, 1, "農(nóng)夫羊 | 狼菜"));
        arrayList.add(new Vertex(1, 0, 1, 1, "狼 | 農(nóng)夫羊菜"));
        arrayList.add(new Vertex(1, 1, 0, 1, "羊 | 農(nóng)夫狼菜"));
        arrayList.add(new Vertex(1, 1, 1, 0, "菜 | 農(nóng)夫狼羊"));
        arrayList.add(new Vertex(1, 1, 1, 1, "已經(jīng)全部過河"));
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                arr[i][j] = 0;
            }
        }   // for循環(huán)結(jié)束初始化數(shù)組

        for (int i = 0; i < 10; i++) {
            int temp_i_Man = arrayList.get(i).objState.man;
            int temp_i_Wolf = arrayList.get(i).objState.wolf;
            int temp_i_Sheep = arrayList.get(i).objState.sheep;
            int temp_i_Vegetable = arrayList.get(i).objState.vegetable;
            for (int j = 0; j < 10; j++) {
                int temp_j_Man = arrayList.get(j).objState.man;
                int temp_j_Wolf = arrayList.get(j).objState.wolf;
                int temp_j_Sheep = arrayList.get(j).objState.sheep;
                int temp_j_Vegetable = arrayList.get(j).objState.vegetable;
                if (temp_i_Man != temp_j_Man && (Math.abs(temp_i_Wolf - temp_j_Wolf) +
                        Math.abs(temp_i_Sheep - temp_j_Sheep) +
                        Math.abs(temp_i_Vegetable - temp_j_Vegetable) <= 1)) {
                    // 滿足兩個條件：①man的狀態(tài)不一樣②有且僅有最多一個狼羊菜中的一個對象狀態(tài)不一樣
                    arr[i][j] = 1;          // 滿足以上條件則滿足連通性，置為1
                }
            }
        }


        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                System.out.printf("%2d", arr[i][j]);
            }
            System.out.println();   // 換行操作
        }

        visited[0] = 1;
        dfs(1, 10);         // 從第一個點找最后一個點
    }

    public static void dfs(int start, int end) {
        if (start == end) {
            print(end);    // 調(diào)用print()方法輸出結(jié)果
            System.out.println();
        }

        for (int i = 0; i < 10; i++) {
            if (arr[start-1][i] > 0 && visited[i] == 0) {
                // 有邊且沒有被訪問
                visited[i] = start;
                dfs(i+1, end);
                visited[i] = 0; // 回溯時置為0
            }
        }
    }

    public static void print(int end) {
        // 從最后往前遍歷页响，然后正序輸出
        int[] temp = new int[10]; // 保存了倒敘輸出的順序
        int num = 0;    // num表示要輸出的個數(shù)
        int i = end;    // i表示當前是第幾個數(shù)
        while (i != 1) {
            // 當i不是第一個數(shù)字時篓足，則繼續(xù)往前找
            temp[num] = visited[i - 1];
            i = temp[num];
            num++;      // num加1
        }
        for (int j = num - 1; j > 0; j--) {
            System.out.println(arrayList.get(temp[j] - 1).outputMessage);
        }
        // 輸出最終狀態(tài)
        System.out.println(arrayList.get(9).outputMessage);
    }
}

寫在最后

因為平時都是在用為知筆記在記錄這些學(xué)習(xí)筆記，所以想要直接騰寫過來發(fā)現(xiàn)很費功夫拘泞，格式不太兼容纷纫，還正在想辦法解決這種事...

歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處陪腌！
簡書ID：@我沒有三顆心臟
github：wmyskxz
歡迎關(guān)注公眾微信號：wmyskxz_javaweb
分享自己的Java Web學(xué)習(xí)之路以及各種Java學(xué)習(xí)資料