leetcode 1263问题

Question

老师，你帮我看一下我这道题的解答，我用的就是BFS去求解这个问题，我看不出我代码有什么问题，但就是提交不上去，老师能帮我看一下我的代码存在什么问题吗？码云网址:
https://gitee.com/jin_chen_xi/leetcode_1263__push_box/blob/master/src/leetcode/_1263_推箱子.java

Answer 1

liuyubobobo 2020-03-07 16:03:27

具体算法我没有看，不过我试着提交了一下，现在你的代码提交不上去，是因为 Leetcode 的线上 Java 编译器不支持 javafx 了，import javafx.util.Pair 也不行。你需要自己写一个 Pair 类，来实现 Pair 的功能。

继续加油！：）

• 提问者 Sunny_SunshineX #1

  不是Pair的问题，因为在自己的idea中用它的测试用例执行答案也不是正确答案，是具体算法的问题，老师有时间能不能抽空看一下我的算法逻辑是不是存在什么问题？

• liuyubobobo 回复 提问者 Sunny_SunshineX #2

  抱歉，那你需要向我阐述你的逻辑是什么样子，具体对于什么测试用例，单步跟踪到哪一步，你觉得你的代码里具体哪个变量应该得到什么结果，但是却得到了什么结果，你觉得不明白。我无法做到同学们扔来一个错误的代码，我马上就能调试出正确的代码。这里是问答区，你需要先经过自己的调试，把真正的问题找到。请谅解。如果想参考我的思路，可以参考这里（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/1263-Minimum-Moves-to-Move-a-Box-to-Their-Target-Location/cpp-1263/main.cpp 加油！：）

• 提问者 Sunny_SunshineX 回复 liuyubobobo #3

  我的思路是:先确定箱子所在的位置，看箱子所在的位置是否是死角(是否上边和右边是墙或者是边界，是否右边和下边是墙或者是边界，是否下边和左边是墙或者是边界，是否左边和上边是墙或者是边界)，如果是一个死角，则无法推动，直接返回-1，如果可以推动就创建一个dis的HashMap记录盘面状态对应的最小推动箱子的次数，并将原本盘面中的"T"替换为"."(因为在后续的查找所有可能的下一个盘面状态的时候，会进行数组元素的交换，可能会把T这个目标点位置给弄乱了)，然后记录下"T"在盘面字符串中对应的索引(在代码中就是tIndex这个变量)，先将初始的盘面的字符串表示形式放入队列中，接下来开始BFS，对于每一个盘面寻找下一个所有可能的状态的逻辑是这样的：先寻找S也就是玩家的位置，并使用对应的变量保存其x坐标，和y坐标，然后开始进行四联通遍历，对四个方向都进行考察，如果该方向的下一个位置是"."则代表是空地，直接交换S的位置与当前位置的值，再用一个Pair<String, Boolean>封装，Pair的key代表盘面字符串，value代表是否推了箱子，对于下一个位置是"."的情况，就是使用new Pair(str, false)的方式封装，然后放入list中，最后将S的位置与当前位置的值交换回来。如果下一个位置是一个"B"则代表是箱子，那么就要判断推箱子的方向的下一个位置是否越界或者是墙，如果不是，则开始推箱子的过程，推箱子的逻辑：将推箱子的方向的下一个位置设置为"B"，原本箱子的位置设置为"S"，原本"S"的位置设置为'.'，最后也是按照Pair封装，因为此时已经推动了箱子，所以封装成new Pair(str, true)的形式。接下来就是BFS那边的逻辑，BFS的基本套路就不做阐述，就是遍历出集合的每一个值。取出的Pair如果value是true的话，那么代表此时的盘面状态是经过了一次推箱子达到的，那么执行:dis.put(key, dis.get(cur) + 1); 即从当前盘面状态的最小推动次数+1，最后如果key.indexOf("B") == tIndex，即箱子已经推到了目标点的位置，就return dis.get(key);

点开查看后面2条评论