7-5 农夫送狼羊菜JS实现

Question

先上代码：

const LinkedList = require("../../../util/LinkedList");
function RiverPuzzle() {
    var lDeadSet = new Set([120003,23100]), rDeadSet = new Set([100023,3120]), visited = new Set();
    var queue = new LinkedList();
    var step = [];
    var curr = 123;
    var end = '';
    var pre = new Map();
    queue.add(curr);
    visited.add(curr);
    this.path = function () {
        console.log('path: ' + pre);
        var res = [];
        var c = end;
        debugger
        while (c != pre.get(c)) {
            res.push(c);
            c = pre.get(c);
        }
        res.reverse();
        return res;
    }
    var bfs = function () {
        while (!queue.isEmpty()) {
            var cur = queue.remove();
            var nexts = [];
            var i = parseInt(cur % 1000 / 100) * 100;
            var j = parseInt(cur % 100 / 10) * 10;
            var k = parseInt(cur % 10);

            nexts.push(cur - i + i * 1000);
            nexts.push(cur - j + j * 1000);
            nexts.push(cur - k + k * 1000);

            var x = parseInt(cur / 100000) * 100000;
            var y = parseInt((cur - x) / 10000) * 10000;
            var z = parseInt((cur - y) / 1000) * 1000;

            nexts.push(cur - x + x / 1000);
            nexts.push(cur - y + y / 1000);
            nexts.push(cur - z + z / 1000);
            // 从右边往左边运
            if (step.length == 0) {
                for (var i = 0; i < 3; i++) {
                    var next = nexts[i];
                    // 若next没被访问过并且不在死亡数字中
                    if (!visited.has(next) && !rDeadSet.has(next)) {
                        queue.add(next);
                        visited.add(next);
                        pre.set(next, cur);
                        // 运完了后，发现左边有死亡数字，则触发从左边往右边运
                        if (lDeadSet.has(next)) {
                            step.push(1);
                        }
                    }
                    if (next == 123000) {
                        end = next;
                        return;
                    }
                }
            } else {
                for (var i = 3; i < 6; i++) {
                    var next = nexts[i];
                    if (!visited.has(next) && !lDeadSet.has(next)) {
                        queue.add(next);
                        visited.add(next);
                        pre.set(next, cur);
                        step.splice(0,1);
                    }
                    if (next == 123000) {
                        end = next;
                        return;
                    }
                }
            }
        }
    }
    bfs(curr);
}
var river = new RiverPuzzle();
console.log(river.path());

我实现的思路是这样的：采用了老师前面介绍的解密码锁和装水的思路。狼和羊在一边或羊和菜在一边，那么就是死锁，也就是开锁题目的DeadSet，只不过它又是把DeadSet分2部分存储。说它为何又和装水的问题很像呢？是因为河的左岸和右岸可以看成是2个水桶，但是它又和水桶问题又有点区别，区别在于水桶可以从外部接水，我们这个题目它不能从外部引入物件，因为题目只给你3个动物，不会多出别的数据。我们在定义狼是1，羊是2，菜是3，那么这里初始状态就是000123,也就是123，代表动物都在左边岸上，我们要让最终状态是123000。这里注意，数据格式是这样的：xxx,xxx，逗号左边是左岸，右边是右岸，数字移位置只能是：1在百位或者10W位，2只能在十位或万位，3只能在个位和千位来回调换，这样就可以用一个数字来表示状态了。

    nexts数据也分2部分，前3部分数据是从右岸向左岸运动物，后3部分是从左岸向右岸运动物。

    这里右考虑到，加入船和农夫再有死锁对应的岸边，是可以让数据通过验证的，所以我把死锁的状态分为左岸死锁和右岸死锁两部分，举个例子，当我运一只动物到对岸去（从右边数据向左边数据送数据），这时对岸2个动物虽然是不能共存的，但是我们暂时不去管它，只是在step中存入一个状态数据告诉程序农夫在下轮循环中要带一个动物回去，然后在下轮循环处理中农夫会带一个动物回去，也就是从左岸向右岸运动物，当step为空的时候就表示左岸的数据没死锁了，然后在下一轮循环中继续从右岸向左岸运动物，知道达到终止状态程序结束。

    程序的其它部分和之前的代码一样，没什么好说的。

    刚看了别人的代码发现我这里只需要01占位就可以了。

Answer 1

liuyubobobo 2022-07-14 08:39:24

赞！

其实当能够熟练使用 BFS 的时候，剩下的问题主要就是“状态的定义”和“状态转移的定义”了。所谓“状态的定义”，就是定义清楚图的点是什么；所谓“状态转移的定义”，就是定义清楚图的边是什么。也就是如何根据问题背景，建立这个图，说得更广义一些，就是问题的建模。

实际上，不仅仅是 BFS 相关的问题是如此，大部分问题都是如此。很多时候，问题的关键是建模，而不是这些最 basic 的 technique 的使用。当然，这些最 basic 的 tachnique，比如 BFS，是基础。

继续加油！：）

• 提问者 qq_crusader_1 #1

  是这样的，总结了几点：1）把这些数组转换成一个数字状态 2）找到初始状态 3）找到终止状态 4）找到转换过程 4）矛盾点，也就是deadSet。谢谢老师