Leetcode 1263 推箱子
老师，推箱子这道题， 箱子从源点到目标点最少步数，显而易见是BFS方法去做，但是加了人去推动箱子，我就没辙了，看了官方题解，也没懂，可以讲下思路吗： ）
==========================================================
老师，你讲的 【人，箱子】作为一个图节点，这个我懂了，然后我写了下面的代码，没写完，因为 当取出queue队列的节点后，
即当前节点, [nowPlayerR, nowPlayerC, nowBoxR, nowBoxC], 然后目前只有一个dirs列表线索，我要怎么取得当前节点的相邻节点?
===============================
老师，整个逻辑我都写在下面了，没通过，我自己也没想法了，能从我的代码里看出是哪里出了问题吗。。。。
/**
* @param {character[][]} grid
* @return {number}
*/
var minPushBox = function(grid) {
const dirs = [ [1, 0], [-1, 0], [0, 1], [0, -1] ];
let playerR, playerC, boxR, boxC, targetR, targetC;
for( let r = 0; r < grid.length; r ++ ){
for( let c = 0; c < grid[0].length; c ++ ){
if( grid[r][c] == 'S' ){ // 玩家 player
playerR = r;
playerC = c;
grid[r][c]='.'
}else if( grid[r][c] == 'B' ){ // 箱子 Box
boxR = r;
boxC = c;
grid[r][c]='.'
}else if( grid[r][c] == 'T' ){ // 目标位置Target
targetR = r;
targetC = c;
grid[r][c]='.'
}
} // for c
} // for r
let queue = []; // bfs队列
let visited = {}; // [人, 箱子]是否访问过 查找表
let step={}; // 统计步数
let res = 0; // 最终答案
queue.push( [playerR, playerC, boxR, boxC] );
visited[`${playerR}-${playerC}-${boxR}-${boxC}`] = true;
step[`${playerR}-${playerC}-${boxR}-${boxC}`] = 0;
while( queue.length > 0 ){
let [nowPlayerR, nowPlayerC, nowBoxR, nowBoxC] = queue.shift(); // 出队列
if( nowBoxR == targetR && nowBoxC == targetC ){ // 说明箱子被推到了目的地
//
return step[`${nowPlayerR}-${nowPlayerC}-${nowBoxR}-${nowBoxC}`]; // 返回
}
// 接下来要得到 [nowPlayerR, nowPlayerC, nowBoxR, nowBoxC]的相邻状态 ???, 要怎么得到
for( let i = 0; i < 4; i ++ ){
let nextPlayerR = nowPlayerR + dirs[i][0], nextPlayerC = nowPlayerC + dirs[i][1];
if( !isInArea(grid, nextPlayerR, nextPlayerC) ){
continue;
}
// 查看玩家目前是否走到了箱子的位置,如果是,则就可以推动箱子, 然后推完后,再次检查箱子的位置是否合法
if( nextPlayerR == nowBoxC && nextPlayerC == nowBoxC ){
let nextBoxR = nowBoxR + dirs[i][0];
let nextBoxC = nowBoxC + dirs[i][1];
// 箱子位置是否合法
if( !isInArea(grid, nextBoxR, nextBoxC) ){
continue;
}
// 检查 [nextPlayerR, nextPlayerC, nextBoxR, nextBoxC]之前有没有考察过
if( visited[`${nextPlayerR}-${nextPlayerC}-${nextBoxR}-${nextBoxC}`] ){
continue;
}
// 进队列
queue.push( [nextPlayerR, nextPlayerC, nextBoxR, nextBoxC] );
visited[`${nextPlayerR}-${nextPlayerC}-${nextBoxR}-${nextBoxC}`] = true; // 更新查找表
step[`${nextPlayerR}-${nextPlayerC}-${nextBoxR}-${nextBoxC}`] = step[`${nowPlayerR}-${nowPlayerC}-${nowBoxR}-${nowBoxC}`] + 1; // 更新步数
}else{
// 说明人和箱子间有距离,人还没够着箱子
// 检查 [nextPlayerR, nextPlayerC, nowBoxR, nowBoxC]之前有没有考察过
if( visited[`${nextPlayerR}-${nextPlayerC}-${nowBoxR}-${nowBoxC}`] ){
continue;
}
// 进队列
queue.push( [nextPlayerR, nextPlayerC, nowBoxR, nowBoxC] );
visited[`${nextPlayerR}-${nextPlayerC}-${nowBoxR}-${nowBoxC}`] = true; // 更新查找表
step[`${nextPlayerR}-${nextPlayerC}-${nowBoxR}-${nowBoxC}`] = step[`${nowPlayerR}-${nowPlayerC}-${nowBoxR}-${nowBoxC}`] + 1; // 更新步数
}
} // for i dirs
} // end while queue.length > 0
return -1; // 说明无法做到
};
function isInArea( grid, r, c ){
if( r < 0 || r >= grid.length ){
return false;
}
if( c < 0 || c >= grid[0].length ){
return false;
}
return grid[r][c] == '.'
}
正在回答
2回答
代码思路和注解写的非常清楚，赞一下。
以下是基于你的代码我修改的可以 AC 的代码：
几点修改：在下面的代码中，我用 ///!!!!!!! 的形式注释了：
1）
一个“弱智错误”，把 nowBoxR 写成了 nowBoxC
2）
修改了上面的错误，你的程序逻辑就没问题了。但是，题目要求求出了最少“推了”多少次，你的代码求出来的是走多少步（人不推箱子，只走格子，也计数了。但是题目要求不计数。）
所以，注释 2 的地方不再 +1。
3）
非常重要的，在修改了 2）的基础上，现在一般的 bfs 不再 work 了。因为此时，这个图不再是无权图了，而是带权图：有的步数权值为 1（推箱子的情况）；有的步数权值为 0（不推箱子的情况）。
对于带权图，当然可以直接使用 dijkstra 解决。但是，对于一张图，图中的边的权值，或者为 0，或者为 1，可以使用一种“特殊”的算法求解其最短路。这个算法叫 0-1 bfs。很可惜，我的课程中没有介绍这个算法，但其实这个算法如果理解了 bfs 和 dijkstra 的话，就很简单。下面简单叙述一下：
回忆一下 dijkstra 算法，其本质在于每次要取出当前求出路径的最短的顶点，在这个基础上做 relax。因此我们要使用优先队列，每次求出当前最短路的点。
但是如果一张图的边的权值或 0 或 1，那么权值为 0 的边对到这个点的路径长度没有贡献，所以，权值为 0 的边对应的点一定在优先队列的顶端；而权值为 1 的点延长了最长路径，所以一定在优先队列的末尾。这样一来，我们完全可以不使用优先队列，只使用普通队列就够了。遇到权值为 0 的边，把这个顶点扔到队首；遇到权值为 1 的边，把这个顶点扔到队尾就好。达到了和优先队列同样的效果。
这样的一个思路可以非常简单的基于 bfs 的代码修改得到（所以叫 0-1 bfs 而不是 0-1 dijkstra），我们只需要对于权值为 0 的边，入队的方式从队尾入队修改为队首入队就好了。严格意义上，此时这个数据结构已经不是普通的队列（queue）了，而是双端队列（deque）。但是 js 不区分这两种结构，都使用 Array，也就无所谓了。具体，在下面的注释 3） 处，我将 push 修改为 unshift，就是 0-1 bfs 了。
==========
上面对 0-1 bfs 的介绍比较粗糙，如果感兴趣，可以在网上再搜索一下，学习一下介绍的更详细的文章。
但依然是，使用 0-1 bfs 解决这个问题只是一个 plus。如果不了解 0-1 bfs，把这个问题抽象成为一个带权图的最短路径问题以后，使用 dijkstra 完全没有问题。
继续加油！：）
/**
* @param {character[][]} grid
* @return {number}
*/
var minPushBox = function(grid) {
const dirs = [ [1, 0], [-1, 0], [0, 1], [0, -1] ];
let playerR, playerC, boxR, boxC, targetR, targetC;
for( let r = 0; r < grid.length; r ++ ){
for( let c = 0; c < grid[0].length; c ++ ){
if( grid[r][c] == 'S' ){ // 玩家 player
playerR = r;
playerC = c;
grid[r][c]='.'
}else if( grid[r][c] == 'B' ){ // 箱子 Box
boxR = r;
boxC = c;
grid[r][c]='.'
}else if( grid[r][c] == 'T' ){ // 目标位置Target
targetR = r;
targetC = c;
grid[r][c]='.'
}
} // for c
} // for r
let queue = []; // bfs队列
let visited = {}; // [人, 箱子]是否访问过 查找表
let step={}; // 统计步数
let res = 0; // 最终答案
queue.push( [playerR, playerC, boxR, boxC] );
visited[`${playerR}-${playerC}-${boxR}-${boxC}`] = true;
step[`${playerR}-${playerC}-${boxR}-${boxC}`] = 0;
while( queue.length > 0 ){
let [nowPlayerR, nowPlayerC, nowBoxR, nowBoxC] = queue.shift(); // 出队列
console.log([nowPlayerR, nowPlayerC, nowBoxR, nowBoxC])
if( nowBoxR == targetR && nowBoxC == targetC ){ // 说明箱子被推到了目的地
//
return step[`${nowPlayerR}-${nowPlayerC}-${nowBoxR}-${nowBoxC}`]; // 返回
}
// 接下来要得到 [nowPlayerR, nowPlayerC, nowBoxR, nowBoxC]的相邻状态 ???, 要怎么得到
for( let i = 0; i < 4; i ++ ){
let nextPlayerR = nowPlayerR + dirs[i][0], nextPlayerC = nowPlayerC + dirs[i][1];
if( !isInArea(grid, nextPlayerR, nextPlayerC) ){
continue;
}
// 查看玩家目前是否走到了箱子的位置,如果是,则就可以推动箱子, 然后推完后,再次检查箱子的位置是否合法
///!!!!!!!!!! 1. 原本代码写成了 nowBoxR !!!!!!!!!!///
if( nextPlayerR == nowBoxR && nextPlayerC == nowBoxC ){
let nextBoxR = nowBoxR + dirs[i][0];
let nextBoxC = nowBoxC + dirs[i][1];
// 箱子位置是否合法
if( !isInArea(grid, nextBoxR, nextBoxC) ){
continue;
}
// 检查 [nextPlayerR, nextPlayerC, nextBoxR, nextBoxC]之前有没有考察过
if( visited[`${nextPlayerR}-${nextPlayerC}-${nextBoxR}-${nextBoxC}`] ){
continue;
}
// 进队列
queue.push( [nextPlayerR, nextPlayerC, nextBoxR, nextBoxC] );
visited[`${nextPlayerR}-${nextPlayerC}-${nextBoxR}-${nextBoxC}`] = true; // 更新查找表
step[`${nextPlayerR}-${nextPlayerC}-${nextBoxR}-${nextBoxC}`] = step[`${nowPlayerR}-${nowPlayerC}-${nowBoxR}-${nowBoxC}`] + 1; // 更新步数
}
else{
// 说明人和箱子间有距离,人还没够着箱子
// 检查 [nextPlayerR, nextPlayerC, nowBoxR, nowBoxC]之前有没有考察过
if( visited[`${nextPlayerR}-${nextPlayerC}-${nowBoxR}-${nowBoxC}`] ){
continue;
}
// 进队列
///!!!!!!!!!! 3. 此时从队首入队 !!!!!!!!!!///
queue.unshift( [nextPlayerR, nextPlayerC, nowBoxR, nowBoxC] );
visited[`${nextPlayerR}-${nextPlayerC}-${nowBoxR}-${nowBoxC}`] = true; // 更新查找表
///!!!!!!!!!! 2. 此时，step 不 +1. !!!!!!!!!!///
step[`${nextPlayerR}-${nextPlayerC}-${nowBoxR}-${nowBoxC}`] = step[`${nowPlayerR}-${nowPlayerC}-${nowBoxR}-${nowBoxC}`]; // 更新步数
}
} // for i dirs
} // end while queue.length > 0
return -1; // 说明无法做到
};
function isInArea( grid, r, c ){
if( r < 0 || r >= grid.length ){
return false;
}
if( c < 0 || c >= grid[0].length ){
return false;
}
return grid[r][c] == '.'
}
-
只有人可以向四个方向挪动，人挪动一步，如果能推动箱子，箱子的位置也要改变，就得到了下一个状态。
有任何疑惑可以回复我~ 2023-05-10 03:54:45 -
老师，我自己的代码写了下，算是对整个逻辑都去实现了，没通过，我一下子也想不出来我这的代码哪里出了问题，老师您指正一下哈：）
有任何疑惑可以回复我~ 2023-05-10 18:21:51
相似问题
登录后可查看更多问答，登录/注册
