首页 > 试题广场 >

编程题1

[编程题]编程题1
  • 热度指数:222 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
有一个推箱子的游戏, 一开始的情况如下图:

上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;

..S0.. -> ...S0.

注意不能将箱子推动到'#'上, 也不能将箱子推出边界;

现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。


输入描述:
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);
后面为n行字符串,每行字符串有m字符, 表示游戏盘面;


输出描述:
一个数字,表示最少几步能完成游戏,如果不能,输出-1;
示例1

输入

3 6
.S#..E
.#.0..
......

输出

11
思路:利用广度搜索求最短路径,队列中的每个位置是人的位置和箱子的位置的集合,用四维数组记录走过的路程状态。首先判断人是否已经走到箱子了,位置重合时带箱子一起走,直到箱子的位置和终点的位置重合,输出路程。
代码:
let [n,m] = readline().split(' ').map(item=>Number(item));
let map = [],start={},end={};
for(let i=0;i<n;i++){
    let line = readline().split('')
    map.push(line)
    let fstart = line.indexOf('S'),fend = line.indexOf('E'),fbox = line.indexOf('0');
    if(fstart !== -1){
        start.px = i;
        start.py = fstart;
    }
    if(fend !== -1){
        end.x = i;
        end.y = fend;
    }
    if(fbox !== -1){
        start.bx = i;
        start.by = fbox;
    }
}
//初始化搜索队列和记录步数的四维数组
let queue = [start], location=[];
for(let i=0;i<n;i++){
    location[i]=[]; 
    for(let j=0;j<m;j++){
        location[i][j]=[];
        for(let k=0;k<n;k++){
            location[i][j][k]=[]
            for(let p=0;p<m;p++){
                location[i][j][k][p]=-1
            }
        }
    }
}
location[start.px][start.py][start.bx][start.by]=0
//移动数组
const walk = [{x:0,y:1},{x:0,y:-1},{x:1,y:0},{x:-1,y:0}]
let now={}//存储当前人和箱子的位置
while(queue.length){
    now = queue.shift();
    //如果到达终点,则输出
    if(now.bx === end.x && now.by === end.y){
        console.log(location[now.px][now.py][now.bx][now.by]);
        break;
    }
    for(let move of walk){
        //移动人,判断人越界
        let player={x:now.px+move.x, y:now.py+move.y}
        if(player.x>=0 && player.x<n && player.y>=0 && player.y<m && map[player.x][player.y]!=='#'){
            let box = {}
            //如果移动后人与箱子重合,也移动箱子
            if(player.x === now.bx && player.y === now.by){
                //判断箱子越界
                box={x:now.bx+move.x, y:now.by+move.y}
                if(box.x<0 || box.x>=n || box.y<0 || box.y>=m || map[box.x][box.y]==='#'){
                    continue;
                }
            }
            //如果不重合,箱子不动
            else{
                box.x = now.bx;
                box.y = now.by;
            }
            //是否已经遍历过
            if(location[player.x][player.y][box.x][box.y]<0){
                queue.push({px:player.x,py:player.y,bx:box.x,by:box.y});
                location[player.x][player.y][box.x][box.y] = location[now.px][now.py][now.bx][now.by]+1;
            }
        }
      }  
    
}
if(now.bx!==end.x || now.by!==end.y){
    console.log(-1)
}

发表于 2020-06-30 12:23:58 回复(0)
超出内存了,谁来救救我
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
let k = -1;
let maxCol;
let row = [];
let temp = [];
let S, E, Box;
let mask;
let que = [];
let flag = false;
rl.on('line', line => {
    if (k < 0) {
        temp = line.trim().split(' ');
        k = Number.parseInt(temp[0]);
        maxCol = Number.parseInt(temp[1]);
        mask = new Array(k); // (x,y,xb,xy)->{step, status}
        for (let i = 0; i < k; i++) {
            // let temp = {step:0,step1:0,status0:true,status1:true} // 这样子同一row的对象引用相同
            mask[i] = new Array(maxCol);  // x
            for (let j = 0; j < maxCol; j++) {
                mask[i][j] = new Array(k); // y
                for (let ii = 0; ii < k; ii++) {
                    mask[i][j][ii] = new Array(maxCol);  // xb
                    for (let jj = 0; jj < maxCol; jj++) {
                        let temp = {step:0,status:true}   // yb  每次指向的引用不同
                        mask[i][j][ii][jj] = temp;
                    }
                }
            }
        }
    } else {
        temp = line.split('');
        for (let i = 0, len = temp.length; i < len; i++) {
            if (S === undefined || E === undefined || Box === undefined) {
                if (temp[i] === 'S') {
                    S = [row.length, i];
                } else if (temp[i] === 'E') {
                    E = [row.length, i];
                } else if (temp[i] === '0') {
                    Box = [row.length, i];
                }
            } else {
                break;
            }
        }
        row.push(temp);
        if (k === row.length) {
            temp = null;
            let direct = [1, -1, 1, -1];
            let beforeEnd;
            let d;
            let cur
            que.push([S[0], S[1], Box[0], Box[1]]);
            mask[ S[0] ][ S[1] ][ Box[0] ][ Box[1] ].status = false; // 人-箱子 -> 终点
            while (que.length !== 0) {
                cur = que.shift(); // [y, x, yb, yx]
                for (let i = 0; i < 4; i++) { // 当前一步内能到的的点
                    let to = [0, 0, cur[2], cur[3]];
                    // 找到箱子前
                    if (i < 2) { // x
                        to[0] = cur[0];
                        to[1] = cur[1] + direct[i];
                    } else { // y
                        to[0] = cur[0] + direct[i];
                        to[1] = cur[1];
                    }
                    if (to[0] === to[2] && to[1] === to[3]) {
                        d = [to[2]-cur[0], to[3]-cur[1]]; // row col
                        if (d[0] === 0) { // row is same
                            if (d[1] > 0) { // box的左边
                                to = [to[0], to[1], to[0], to[1]+1];
                                // Box = [Box[0], Box[1] + 1]
                            } else {
                                to = [to[0], to[1], to[0], to[1]-1];
                                // Box = [Box[0], Box[1] - 1]
                            }
                        } else { // col is same
                            if (d[0] > 0) { // box的左边
                                to = [to[0], to[1], to[0]+1, to[1]];
                                // Box = [Box[0]+1, Box[1]]
                            } else {
                                to = [to[0], to[1], to[0]-1, to[1]];
                                // Box = [Box[0]-1, Box[1]]
                            }
                        }
                    }
                    if (0<=to[0] && to[0]<k && 0<=to[1] && to[1]<maxCol && 0<=to[2] && to[2]<k && 0<=to[3] && to[3]<maxCol
                        && mask[to[0]][to[1]][to[2]][to[3]].status && row[to[0]][to[1]]!== '#' && row[to[2]][to[3]]!== '#') { 
                        // 不为墙 在边界内
                        mask[to[0]][to[1]][to[2]][to[3]].status = false;
                        mask[to[0]][to[1]][to[2]][to[3]].step = mask[cur[0]][cur[1]][cur[2]][cur[3]].step +1;
                        que.push(to);
                        if (to[2] === E[0] && to[3] === E[1]) {
                            beforeEnd = cur;
                            flag = true;
                            que = null;
                            break;
                        }
                    }
                    to = null;
                }
                if (flag) {
                    console.log(mask[beforeEnd[0]][beforeEnd[1]][beforeEnd[2]][beforeEnd[3]].step + 1);
                    mask = null;
                    break;
                }
            }
            if (!flag) {
                console.log(-1); // 没找着
            }
        }
    }
})


发表于 2021-04-02 00:20:33 回复(0)