1. 火车进站

求N列火车进出站的顺序组合

重点：每次可以选择1列进站或1列出站，当选择情况1或情况2时，它们的初始条件应该是相同的，这也是为什么每种情况操作完之后需要进行条件恢复的原因

let trains = ['1', '2', '3'] // 求3列火车进出站的顺序组合

let lth = trains.length;
let stack = [],
    res = []; // 存放出站顺序
let dfs = function (leftArr) {
    if (res.length === lth) {
        console.log(res);
        return;
    }
    // 因为进站和出站这2种选择是并列的，
    // 所以当选了第一种时，操作完后需要将数据恢复，以保证选2和选1的初始条件是相同的
    if (leftArr.length) { // 可以选择一个进站
        let v = leftArr.shift();
        stack.push(v); // 火车进站
        // console.log(v, '进')
        dfs(leftArr);
        leftArr.unshift(stack.pop()); // 恢复
    }
    if (stack.length) { // 或者选择一个出站
        let v = stack.pop(); // 出站
        // console.log(v, '出')
        res.push(v);
        dfs(leftArr);
        stack.push(v); // 恢复
        res.pop(); // 注意res也要恢复
    }
}
dfs(trains);

2. 迷宫问题

• 确认终止条件（一般根据结果是否收集结束判断）
• 枚举可选值
• 遍历每个值，在当前值下收集结果，并dfs下一轮，当前值的条件深度遍历完之后，恢复res收集器到循环前的状态。因为要确保循环中的每一个值的初始条件是一样的，循环的每一个值都是一种选择

let [row, col] = arr.shift(); // 迷宫行和列
let res = [];
function dfs(i, j) {
    if (i === row - 1 && j === col - 1) { // 确定终止条件
        res.push([i, j]);
        res.forEach(r => {
            console.log(`(${r[0]},${r[1]})`);
        });
        return;
    }
    // [i][j]
    let options = []; // 收集本轮的可选值
    if (i > 0 && arr[i - 1][j] === '0') {
        // [i - 1][j] // 上
        options.push([i - 1, j]);
    }
    if (j < col - 1 && arr[i][j + 1] === '0') {
        // [i][j + 1] // 右
        options.push([i, j + 1]);
    }
    if (j > 0 && arr[i][j - 1] === '0') {
        // [i][j - 1] // 左
        options.push([i, j - 1]);
    }
    if (i < row - 1 && arr[i + 1][j] === '0') {
        // [i + i][j]  // 下
        options.push([i + 1, j]);
    }
    if (res.length) { // 过滤可选值——上一步走过的下一步就不走了
        let last = res[res.length - 1];
        options = options.filter(op => {
            return !(op[0] == last[0] && op[1] == last[1]);
        });
    }
    if (options.length) {
        options.forEach((op) => {
            let [m, n] = op;
            res.push([i, j]); // 记录当前格子
            dfs(m, n); // 从下个格子开始
            res.pop(); // res恢复
        });
    }
}
dfs(0, 0)

3. 数独

依次往每个空格子里填入1-9，这个题需要注意dfs的返回值

function dfs() { // 返回一个布尔值
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (arr[i][j] == 0) { // 如果当前是空格子
                for (let k = 1; k <= 9; k++) { // 依次校验1-9是否可以填入，可以就填
                    if (checkIsValid(i, j, k)) { // 校验arr[i][j]是否可以放入k
                        arr[i][j] = k; // 尝试放入
                        let res = dfs(); // 如果返回true，表示这个格子填了k之后其他格子都填数成功，那么不需要再往后走了
                        if (res) { return true }
                        arr[i][j] = 0; // 否则就恢复数据，并继续下一轮尝试                  
                    }
                }
                // 表示填1-9都不行，表示这个数独本身无解
                return false;
            }
        }
    }
    return true; // 表示每一个格子都有数
}

function checkIsValid(i, j, k) { // 检验arr[i][j]的格子是否可以放入k
    if (arr[i].find(r => r == k)) { // 同行不能重复
        return false;
    }
    for (let r = 0; r < 9; r++) {
        if (arr[r][j] == k) { // 同列不能重复
            return false;
        }
    }
    // 9宫格内不重复
    let rStart = Math.floor(i / 3) * 3, 
        cStart = Math.floor(j / 3) * 3;

    let rEnd = rStart + 2, cEnd = cStart + 2;
    while (rStart <= rEnd) {
        let cs = cStart;
        while (cs <= cEnd) {
            if (arr[rStart][cs] == k) {
                return false;
            }
            cs++
        }
        rStart++;
    }
    return true
}

4. 岛屿数量

image.png

这个题最重要的一步：要想统计1聚集的堆数而不重复统计，那每次找到一堆相邻的1，就将其全部改成0

let count = 0;
function dfs(rIndex, cIndex) {
    let row = grid[rIndex]
    grid[rIndex][cIndex] = 0; // 为了不重复读取1，就把已经读取过的1置为0
    // 左
    if (cIndex > 0 && row[cIndex - 1] == 1) {
        dfs(rIndex, cIndex - 1);
    }
    // 右
    if (cIndex + 1 < row.length && row[cIndex + 1] == 1) {
        dfs(rIndex, cIndex + 1);
    }
    // 上
    if (rIndex > 0 && grid[rIndex - 1][cIndex] == 1) {
        dfs(rIndex - 1, cIndex);
    }
    // 下
    if (rIndex + 1 < grid.length && grid[rIndex + 1][cIndex] == 1) {
        dfs(rIndex + 1, cIndex);
    }
}
grid.forEach((row, rIndex) => {
    row.forEach((item, cIndex) => {
        if (item == 1) {
            // 之所以在这里就能增加count是因为下面的dfs会把和这个1相连的岛屿都置为0
            count++; 
            dfs(rIndex, cIndex);
        }
    });
});


console.log(count)

5. N皇后问题

image.png

这个题要一行一行尝试（而不是在格子维度上），在一行中选一个格子放皇后，再dfs下一行

let grid = [];
let res = [];
let count = 0;
function dfs(rowIndex) {
    if (res.length == n) {
        count++;
        return;
    }
    if (rowIndex === n) { // 边界
        return;
    }
    for (let j = 0; j < n; j++) { // 在当前行中选一个格子
        if (isValid(rowIndex, j)) { // 如果能放的话
            grid[rowIndex][j] = 1; // 放入皇后
            res.push([rowIndex, j]) // 收集结果
            dfs(rowIndex + 1); // 在当前结果下进入下一行去选格子
            grid[rowIndex][j] = 0; // 恢复
            res.pop(); // 恢复
        }
    }
}

for (let i = 0; i < n; i++) {
    grid[i] = new Array(n);
}

dfs(0);

检查是否能在grid[i][j]位置上放皇后

function isValid(i, j) {
    let row = grid[i];
    if (row[j] == 1) { // 格子已经是皇后了
        return false;
    }
    if (row.find(r => r == 1)) {
        // 不能在同一列
        return false;
    }
    for (let r of grid) {
        // 不能在同一行
        if (r[j] == 1) {
            return false;
        }
    }

    // 以下校验不能在同一条斜线
    let level = 1;
    while (i - level >= 0 && j - level >= 0) {
        // 左上
        if (grid[i - level][j - level] == 1) {
            return false;
        }
        level += 1;
    }

    level = 1;
    while (i - level >= 0 && j + level < n) {
        // 右上 i-1 j+1 i-2 j+2
        if (grid[i - level][j + level] == 1) {
            return false;
        }
        level++;
    }

    level = 1;
    while (j - level >= 0 && i + level < n) {
        // 左下 i+1 j-1 i+2 j-2
        if (grid[i + level][j - level] == 1) {
            return false;
        }
        level++;
    }

    level = 1;
    while (j + level < n && i + level < n) {
        // 右下 i+1 j+1 i+2 j+2
        if (grid[i + level][j + level] == 1) {
            return false;
        }
        level++;
    }
    return true;
}

6. 全排列

var arr = ['A', 'B', 'V', ];
var res = [];
function dfs() {
    if (res.length === 3) {
        console.log(res.join(' '));
        return;
    }
    for (let item of arr) { // 每一次可选值都是arr里剩余的元素
        res.push(arr.shift());
        dfs();
        arr.push(res.pop());
    }
}
dfs();

7. 传球

M个人相互传球，由甲开始，经过N次传球后，球仍回到甲手中，则不同的传球方式共有多少种？

/**
 * @param {Array} members 队员 
 * @param {Number} count 传球次数
 */
function pass(members, count) {
    const target = members[0]; // 从第一人开始传，最后回到第一个手上
    let result = [target]; // 球从第1个人手上传出去
    let lth = count + 1; // 例如传3次球，result里会有4个人
    const dfs = function (arr, self) {
        if (result.length === lth) { // 次数到了，如果最后一个人是target，就输出
            if (result[result.length - 1] === target) {
                console.log(result.join(' > '));
            }
            return;
        }
        arr.forEach(item => {
            if (item === self) { return; } // 不能传递给自己
            result.push(item);
            count--; // push了一项就表示传了1次，则总次数-1
            dfs(arr, item);
            result.pop();
            count++;
        })
    }
    dfs(members, target);
}


pass(['甲', '乙', '丙'], 5)