首页 / 题库

P100004 - 推箱子

基础算法
通过次数0 提交次数0 内存限制 512MB 时间限制1秒

描述

「推箱子」是一款风靡全球的益智小游戏,玩家需要将箱子推到仓库中的目标位置。 
游戏地图用大小为 m x n 的网格 表示,其中每个元素可以是墙、地板或者是箱子。 
现在你将作为玩家参与游戏,按规则将箱子 'B' 移动到目标位置 'T' : 
玩家的起始位置用字符 'S' 表示,只要他在地板上,就可以在网格中向上、下、左、右四个方向移动。玩家的起始位置也是地板。 
地板用字符 '.' 表示,意味着可以自由行走。 
墙用字符 '#' 表示,意味着障碍物,不能通行。  
箱子仅有一个,用字符 'B' 表示。相应地,网格上有一个目标位置 'T'。 
玩家需要站在箱子旁边,然后沿着箱子的方向进行移动,此时箱子会被移动到相邻的地板单元格。记作一次「推动」。 
玩家无法越过箱子。 
返回将**箱子推到目标位置的最小 推动 次数**,如果无法做到,请输出 -1。 

输入

第一行有两个数字m,n。表示地图为m行n列。 

第二行开始到m+1行,每一行有n个字符,为'#','.','S','B','T'的其中一种,意义见题目描述。另外保证题目的最外层字符必定是'#'

输出

只有一个数字**箱子推到目标位置的最小 推动 次数**,如果无法做到,请输出 -1。

样例

  • 复制
  • 复制

提示

样例对应的图解释:

$5 \leq n,m \leq 60 $

保证最外层都是#,保证每个测试数据'S','B','T'均出现一次

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36