本文共 2467 字，大约阅读时间需要 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/