1、題目描述

【羊、狼、農(nóng)夫過河】
羊、狼、農(nóng)夫都在岸邊，當(dāng)羊的數(shù)量小于狼的數(shù)量時(shí)，狼會(huì)攻擊羊，農(nóng)夫則會(huì)損失羊。農(nóng)夫有一艘容量固定的船，能夠承載固定數(shù)量的動(dòng)物。要求求出不損失羊情況下將全部羊和狼運(yùn)到對(duì)岸需要的最小次數(shù)。只計(jì)算農(nóng)夫去對(duì)岸的次數(shù)，回程時(shí)農(nóng)夫不會(huì)運(yùn)送羊和狼。
備注：農(nóng)夫在或農(nóng)夫離開后羊的數(shù)量大于狼的數(shù)量時(shí)狼不會(huì)攻擊羊。農(nóng)夫自身不占用船的容量。

【輸入描述】
第一行輸入為M，N，X， 分別代表羊的數(shù)量，狼的數(shù)量，小船的容量。

【輸出描述】
輸出不損失羊情況下將全部羊和狼運(yùn)到對(duì)岸需要的最小次數(shù)（若無法滿足條件則輸出0）。

【示例1】
輸入: 5 3 3
輸出: 3
說明:第一次運(yùn)2只狼第二次運(yùn)3只羊第三次運(yùn)2只羊和1只狼

【示例2】
輸入: 5 4 1
輸出: 0
說明:如果找不到不損失羊的運(yùn)送方案，輸出0

2、解題思路

初始化一個(gè)變量minTimes為(羊數(shù)量+狼數(shù)量) *小船容量;
定義一個(gè)回溯DFS方法, 用于模擬過河的過程，每次遞歸計(jì)算 當(dāng)前狀態(tài)下的最小運(yùn)輸次數(shù);
在DFS函數(shù)中，遍歷嘗試所有可能的運(yùn)輸組合,保證組合中羊的數(shù)量大于等于狼的數(shù)量,以防止羊被狼吃掉;
在遞歸過程中，如果發(fā)現(xiàn)某種組合能夠使得所有羊和狼都運(yùn)到對(duì)岸，且所需次數(shù)小于當(dāng)前記錄的最小次數(shù),則更新最小次數(shù);
后輸出最小運(yùn)輸次數(shù)。如果沒有找到滿足條件的運(yùn)輸方案，輸出0。

3、參考代碼

import java.util.Scanner;

public class 羊狼農(nóng)夫過河 {
    public static int minTimes = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int m = in.nextInt();  // 羊數(shù)量
            int n = in.nextInt();  // 狼數(shù)量
            int x = in.nextInt();  // 小船數(shù)量
            minTimes = 0;
            dfs(m, n, x, 0, 0, 0);

            if (minTimes == Integer.MAX_VALUE) {
                System.out.println(0);
            } else {
                System.out.println(minTimes);
            }
        }
    }

    public static int dfs(int m, int n, int x, int m1, int n1, int times) {
       // 如果小船容量足夠運(yùn)輸所有羊和狼，則只需要一次即可
        if (x >= m + n) {
            if (times + 1 < minTimes) {
                minTimes = times + 1;
            }
            return times + 1;
        }

        // 遍歷所有的運(yùn)輸組合，保證組合中羊的數(shù)量大于狼的數(shù)量
        for (int i = 0; i <= m && i <= x; i++) {
            for (int j = 0; j <= n && i + j <= x; j++) {
                if (i + j == 0) {
                    continue;
                }

                // 船離岸后，原來這岸，要么沒有羊，要么羊比狼多
                if ((m - i == 0 || m - i > n - j) && (m1 + i == 0 || m1 + i > n + j)) {
                    int result = dfs(m, n, x, m - i, n - j, times + 1);
                    if (result < minTimes && result != 0) {
                        minTimes = result;
                    }
                }
            }
        }
        return 0;
    }
}

4、相似題目

（1）代碼隨想錄回溯專題文章來源地址http://www.zghlxwxcb.cn/news/detail-682689.html

到了這里，關(guān)于華為OD機(jī)試真題【羊狼農(nóng)夫過河】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！