博客

题目描述

M行N列的地图, X表示墙, .表示空地, S表示玩家位置, C表示金币, O表示箱子
玩家遇到箱子时, 可以推动箱子(前提是,箱子前面是空地), 一个箱子只能推动一次.
玩家起始位置也是为空地.

算法技巧

1. 用深度优先搜索, 将可直接收集的金币清理掉
2. 用广度优先搜索, 深度将所有可能的箱子推动一遍, 算出最多可收集的金币
3. 遍历箱子, 需要用到回溯技巧

js算法实现
用js写是因为方便在浏览器上直接编程.
打开 https://js.do/, 将以下代码复杂上去, 就可以直接运行了

const X = 'X';  // 墙
const S = 'S';  // 玩家起始位置
const C = 'C';  // 金币
const _ = '.';  // 空地
const O = 'O';  // 箱子
const V = 'V';  // 可访问的空地

// 用于测试的地图, 总共可收集15个金币
const srcMap = [
    '..XC..', 
    '..X.XX',
    'CC.O..', // 2个金币
    'XXX...',
    '......',
    '.OSX..',
    'X.OCX.', // 1个金币
    '...X..',      
    'XXX...',
    '..X...',  
    'C.X...', // 无法收集
    '..X...',  
    'XX....',
    '....OX',
    '...XC.', // 无法收集
    '...XC.',
    '....XX',
    '......', 
    '.....O', // 无法收集
    '....X.', 
    '...XC.',
    '....XX',   
    '......',    
    '......', 
    '.....X', 
    '....OC', 
    '...X.C', // 3个金币
    '..XCOC',   
    '..XXXX',  
    '.....X', 
    '....OC', 
    '...X.C', // 4个金币
    '....OC', //   
    '..XXCX',    
    '....X.', 
    '......', 
    'XX.XXX', 
    'C.OXX.', 
    'CX...C', // 5个金币
    '.X..OC', //   
    '.X.XCX',    
    '....X.',    
];

// 四个方向移动时,x, y方向上的步伐
const dirs = [
    {x: 0, y: -1}, //向上移动
    {x: 0, y: +1, }, //向下移动
    {x: -1, y: 0, }, //向左移动
    {x: +1, y: 0, }, //向右移动
];

// 判断位置是否超出地图
function isOutof(map, xy) {
    return xy.x < 0 || xy.y < 0 || xy.x>=map[0].length || xy.y>=map.length;
}

function print(map) {
    console.log(map);
}

// 复制地图
function clone(map) {
    const newMap = new Array(map.length);
    for(let y = 0; y < map.length; y++) {
        newMap[y] = new Array(map[y].length);
        for(let x = 0; x < map[y].length; x++) {
            newMap[y][x] = map[y][x];
        }
    }
    return newMap;
}

function createArray(width, height) {
    const array = new Array(height);
    for(let y = 0; y < height; y++) {
        array[y] = new Array(width);
    }
    return array;
}

// 使用广度优先搜索收集金币, 同时并标记出哪些位置是可到达的
function bfs(map, startX, startY) {
    let coins = 0;
    let queue = [];

    map[startY][startX] = V;
    queue.push({x: startX, y: startY});

    while(queue.length > 0) {
        const xy = queue.pop();
        for(const dir of dirs) {
            const next = {x: xy.x + dir.x, y: xy.y + dir.y};
            if(isOutof(map, next)) {
                // 超出边界, 或者已经遍历过
                continue;
            }
            const char = map[next.y][next.x];
            switch(char) {
                case C:
                    coins++;
                    map[next.y][next.x] = V;
                    queue.push(next);
                    break;
                case _:
                    map[next.y][next.x] = V;
                    queue.push(next);
                    break;
                case O:
                case X:
                case V:
                    continue;
            }
        }
    }
    return { coins};
}

function dfs(map, startX, startY, boxes) {
    // 收集地图上可达到位置的金币
    let {coins} = bfs(map, startX, startY);

    // 每个箱子可能有4种推法, 全部尝试一遍, 算出最大可能
    let max = 0;

    // 将所有箱子都尝试推一次
    for(const box of boxes) {
        // 上一次递归中, 已经推过了
        if(box.visited) {
            continue;
        }

        box.visited = true;
        // 往4个方向推箱子
        for(const dir of dirs) {
            const playPos = { x: box.x - dir.x, y: box.y - dir.y};
            const pushPos = { x: box.x + dir.x, y: box.y + dir.y};
            // 人和推动后的箱子的位置必须合法
            if(isOutof(map, playPos) || isOutof(map, pushPos)) {
                continue;
            }

            // 箱子前方必须是空地, 箱子后方必须是玩家可达到的位置
            if((map[pushPos.y][pushPos.x] !== _  && map[pushPos.y][pushPos.x] !== V) || 
                map[playPos.y][playPos.x] !== V) {
                continue;
            }
            
            // 箱子位置变成空地, 箱子前方变成墙
            map[box.y][box.x] = _;
            map[pushPos.y][pushPos.x] = X;
            
            // bfs会修改地图, 为了能够回溯
            const collected = dfs(clone(map), box.x, box.y, boxes);
            max = Math.max(max, collected);

            // 回溯: 恢复箱子的状态,
            map[box.y][box.x] = O;
            map[pushPos.y][pushPos.x] = _;   
        }
        // 回溯
        box.visited = false;
    }
    return coins + max;
}

function collectCoints(srcMap) {
    // 初始化为一个二维数组
    let map = [];
    for(const str of srcMap) {
        map.push(str.split(''));
    }
    print(map);
    const width = map[0].length;
    const height = map.length;
    // 找出玩家位置
    let startX;
    let startY;

    // 标记地图中所有的箱子位置
    const boxes = [];

    let foundStartPos = false;
    for(let y = 0; y < height; y++) {
        for(let x = 0; x < width; x++) {
            if (map[y][x] === S) {
                console.log(`start x: ${x} y: ${y}`);
                if(foundStartPos) {
                    console.error('duplicate start position');
                }
                foundStartPos = true;
                startX = x;
                startY = y;
                map[y][x] = _; // 起始位置也是空地
            } else if (map[y][x] === O) {
                boxes.push({ x: x, y: y, visited: false });
            } else if (map[y][x] === _ || map[y][x] === X || map[y][x] === C) {

            } else {
                console.error('invalid char ' + map[y][x]);
            }
        }
    }
    console.log('box count ' + boxes.length);
    const coins = dfs(map, startX, startY, boxes);
    console.log(`coins: ${coins}`);
    return coins;
 }


 let coins = collectCoints(srcMap);
 
 // 浏览器上运行
 document.write(coins);