UVA589 Pushing Boxes

    • 56通过
    • 168提交
  • 题目来源 UVA 589
  • 评测方式 RemoteJudge
  • 标签 广度优先搜索,BFS
  • 难度 省选/NOI-
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    想象一下,你站在一个二维的迷宫里,由方形的格子组成,可能有或者没有被岩石充满。你可以在一个格子上向北、南、东或西移动。这些动作叫做步行。 其中一个空格子包含一个盒子,它可以通过站在盒子旁边,然后在盒子的方向上移动,移动到相邻的空格子。这样的动作叫做推。这个盒子不能用任何其他方式来移动,这意味着如果你把它推到角落里,你就再也不能把它从角落里拿出来。

    其中一个空格子被标记为目标格子。你的工作是把箱子放在目标格子中,通过一系列的行走和推动。由于箱子很重,你想把推的数量减到最少。你能写出一个程序来找出最好的顺序吗?

    输入

    输入包含几个迷宫的描述。每个迷宫描述都包含一个包含两个整数R和C的线段($R,C<=20$),表示迷宫的行数和列数。

    下面是每个包含C字符的R行。每个字符描述迷宫中的一个单元。一个岩石的格子是由一个'#'表示的,一个空的格子由一个'.'表示。你的起始位置用“S”表示,方框的开始位置由“B”和目标格子按“T”表示。

    输入R,C为0 0结束。

    输出

    对于每一个迷宫中的输入,首先打印迷宫的数目,如样本输出所示。然后,如果不可能把盒子带到目标单元格,打印"Impossible."。

    否则,输出一个最小化推送次数的序列。如果有不止一个这样的序列,那么选择一个最小化总移动次数(步行和推送)的序列。如果仍然有不止一个这样的序列,任何一个都是可以接受的。

    将序列打印为字符N、S、E、W、n、s、e和w的字符串,其中大写字母代表推,小写字母代表行走,不同字母代表南北、南、东和西的方向。

    在每个测试用例之后输出一个空行。

    感谢@周子凯 提供翻译

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    输入样例#1: 复制
    1 7
    SB....T
    1 7
    SB..#.T
    7 11
    ###########
    #T##......#
    #.#.#..####
    #....B....#
    #.######..#
    #.....S...#
    ###########
    8 4
    ....
    .##.
    .#..
    .#..
    .#.B
    .##S
    ....
    ###T
    0 0
    输出样例#1: 复制
    Maze #1
    EEEEE
    Maze #2
    Impossible.
    Maze #3
    eennwwWWWWeeeeeesswwwwwwwnNN
    Maze #4
    swwwnnnnnneeesssSSS
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。