有一个推箱子的游戏, 一开始的情况如下图:
上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;
..S0.. -> ...S0.
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
..S0.. -> ...S0.
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);
后面为n行字符串,每行字符串有m字符, 表示游戏盘面;
一个数字,表示最少几步能完成游戏,如果不能,输出-1;
3 6 .S#..E .#.0.. ......
11
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); // 没找着 } } } })