1263. Minimum Moves to Move a Box to Their Target Location

题目信息

题号:

1263

难度:

Hard

主题:

网格、广度优先搜索、推箱子、状态图

原题:

LeetCode 1263

重点:

玩家可以自由行走但不能拉箱子;只有玩家站在箱子相反方向且前方为空时才能推动,答案只统计推动次数

题目重述

给定字符网格:# 表示墙,. 表示空地,S 表示玩家起点,B 表示箱子起点,T 表示目标位置。玩家每次可四向移动到非墙格,不能穿过箱子。

当玩家与箱子相邻且箱子前方一格为空时,可以把箱子向远离玩家的方向推动一格;箱子不能被拉动。请返回把箱子推到目标位置所需的最少推动次数,玩家普通行走不计数。若无法完成,返回 -1。

1 <= grid.length, grid[i].length <= 20,网格中恰好各有一个 S、B 和 T。

自建示例

玩家可以绕到箱子侧面改变推动方向:

输入:grid = [["#","#","#","#","#"],["#","S",".",".","#"],["#",".","B",".","#"],["#",".",".","T","#"],["#","#","#","#","#"]]
输出:2
解释:先把箱子向下推一格,再绕到箱子左侧向右推一格即可到达目标。

箱子周围没有合法推动方向时无解:

输入:grid = [["#","#","#"],["#","B","#"],["#","S","T"]]
输出:-1
解释:箱子向上和向右都是墙,玩家也无法站到其左侧推动,因此不能到达目标。