编程题1

[编程题]编程题1

热度指数：3957 时间限制：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..
......

输出

算法知识视频讲解

牛客题解官

发表于 2020-06-05 17:43:52

题解题目难度：hard 知识点：迷宫搜索类问题，利用BFS找到最短路径。分析：将人所在位置与箱子所在位置以及所走步数看作整体，新建节点Node。首先初始位置入队，通过移动不断将还没有经过的下一位置节点入队，直至找到箱子之前箱子的位置是不变的；当人找到箱子之后（即在箱子的一侧，上下左右），开始推展开全文

17c89

发表于 2023-12-08 14:26:11

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { private static final int[] dX = new int[]{0, 0 展开全文