解决：农夫、狼、羊、菜乘船过河问题

Question

/**
 * 解题思路：开密码锁
 * 用四位表示，第一位狼，第二位羊，第三位菜，第四位人, 0:表示未过河，1：表示已过河
 * 狼，羊，菜，人
 * 0   0   0  0
 *
 * 死锁状态：
 * 0011(羊狼+菜人，羊被吃)
 * 1100(菜人+狼羊，羊被吃)
 * 1001(羊菜+狼人，菜被吃)
 * 0110(狼人+羊菜，菜被吃)
 * 0001(狼羊菜+人，羊被吃)
 * 1110(人+狼羊菜，羊被吃)
 *
 * 初始状态：0000
 * 终止状态：1111
 */
function crossRiver() {
	let startStatus = "0000";
	let visited = new Set();
	let pre = new Map();
	let deads = new Set(["0011", "1100", "1001", "0110", "0001", "1110"]);
	let target = "1111";
	let zeroCode = "0".charCodeAt(0);

	function bfs() {
		let queue = [];
		queue.push(startStatus);
		visited.add(startStatus);

		while (queue.length != 0) {
			let curStatus = queue.shift();
			let arr = curStatus.split("");

			let nexts = [];
			let farmer = arr[arr.length - 1];
			for (let i = arr.length - 1; i >= 0; i--) {
				let originChar = arr[i];
				arr[arr.length - 1] = String.fromCharCode(
					zeroCode + 1 - (originChar.charCodeAt(0) - zeroCode)
				);
				//! 关键点：为农自己可选中自己过河，或者选中带一个东西过河
				if (i === arr.length - 1) {
					nexts.push(arr.join(""));
				} else if (originChar == farmer) {
					//! 说明：需要农户和带的东西在同一侧才可以携带
					arr[i] = String.fromCharCode(
						zeroCode + 1 - (originChar.charCodeAt(0) - zeroCode)
					);
					nexts.push(arr.join(""));
				}
				arr[i] = originChar;
			}

			for (let next of nexts) {
				if (!visited.has(next) && !deads.has(next)) {
					queue.push(next);
					visited.add(next);
					pre.set(next, curStatus);
					if (next == target) {
						return;
					}
				}
			}
		}
	}

	bfs();

	if (!visited.has(target)) {
		return -1;
	}

	let cur = target;
	let path = [];
	while (cur != startStatus) {
		path.push(cur);
		cur = pre.get(cur);
	}

	path.push(startStatus);

	return path.reverse().join("->");
}

let ret = crossRiver();
console.log(ret);

/* 
输出结果：0000->0101->0100->0111->0010->1011->1010->1111
 */

Answer 1

liuyubobobo 2023-02-21 01:07:59

先带羊过河，自带狼过河，羊和狼同时在河对岸，狼会吃掉羊。

继续加油！：）

• 提问者 Potter520 #1

  还以为只要到对面就可以了，忘了考虑在对面会发生这么糟心的事。知道答案了
  初始状态：
  左边          	船               右边
  人狼羊菜   		  
  狼菜	         人羊							 
  狼菜		人                 羊
  狼             人菜               羊
  狼             人羊               菜
  羊             人狼               菜
  羊             人                 菜狼
                 人羊               菜狼
  				菜狼人羊
  
  我想下如何要如何改