本文共 2527 字，大约阅读时间需要 8 分钟。

老农过河问题是一个经典的算法题目，要求通过最少的过河次数，使猫、狗、鱼安全地到达对岸。以下是解决方案的详细分析和代码实现。

问题分析

老农需要每次只带一只动物过河。当老农不在对岸时，必须确保对岸的动物之间没有冲突。如果对岸存在猫和狗，或者猫和鱼，就会发生不和谐的情况。因此，老农必须在过河前确保对岸的和谐状态。

解决思路

代码实现

package com.itheima;
import java.util.LinkedList;
public class River {
    LinkedList
   
     here = new LinkedList<>();
    LinkedList
    
      there = new LinkedList<>();
    String farmer = "老农";
    String cat = "猫";
    String fish = "鱼";
    String dog = "狗";
    int count = 0;
    public void river() {
        here.add(farmer);
        here.add(cat);
        here.add(fish);
        here.add(dog);
        while (!here.isEmpty()) {
            if (here.contains(farmer)) {
                hereRiver();
            } else {
                thereRiver();
            }
        }
        System.out.println("在河的右岸有" + there);
    }
    private void hereRiver() {
        here.remove(farmer);
        String animal = null;
        while ((animal = here.remove()) != null) {
            if (isHarmony(here)) {
                there.add(farmer);
                there.add(animal);
                System.out.println("第" + ++count + "次: 老农带着(" + animal + ")划船过河的右岸");
                return;
            } else {
                here.add(animal);
            }
        }
    }
    private void thereRiver() {
        there.remove(farmer);
        String animal = null;
        if (isHarmony(there)) {
            System.out.println("第" + ++count + "次: 老农[什么都不带]划船回到河的左岸");
            here.add(farmer);
        } else {
            while ((animal = there.remove()) != null) {
                if (isHarmony(there)) {
                    here.add(farmer);
                    here.add(animal);
                    System.out.println("第" + ++count + "次: 老农带着(" + animal + ")划船回到河的左岸");
                    return;
                } else {
                    there.add(animal);
                }
            }
        }
    }
    private boolean isHarmony(LinkedList
     
       list) {
        return !(list.contains(dog) && list.contains(cat)) && !(list.contains(cat) && list.contains(fish));
    }
}
     
    
   

代码解释

• river()：初始化左岸和右岸的队列，开始过河循环。
• hereRiver()：老农在左岸时的过河方法，检查对岸和谐状态，决定是否带动物过河。
• thereRiver()：老农在右岸时的过河方法，先返回左岸，检查对岸和谐状态，决定是否带动物回去。
• isHarmony()：检查对岸是否和谐，返回布尔值，用于过河决策。

通过这种方法，老农可以在最少的过河次数内安全地将所有动物带到对岸，确保对岸的和谐与安全。

转载地址：http://wmgy.baihongyu.com/