{"trustable":false,"sections":[{"title":"题目描述","value":{"format":"HTML","content":"想象一下,你正站在一个由方形细胞组成的二维迷宫中,这些细胞可能充满岩石,也可能没有。您可以一次向北、南、东或西移动一个单元格。这些动作叫做散步。\n\n\u003c/br\u003e\n\n\u003c/br\u003e其中一个空单元格包含一个盒子,可以通过站在盒子旁边然后沿着盒子的方向移动来移动到相邻的自由单元格。这样的动作叫做推。除了推,盒子不能以任何其他方式移动,这意味着如果你把它推到角落里,你就再也不能把它从角落里拉出来了。\n\n\u003c/br\u003e\n\n\u003c/br\u003e其中一个空单元格被标记为目标单元格。你的工作是通过一系列的行走和推动将盒子带到目标细胞。由于箱子很重,你想尽量减少推的次数。你能写一个程序来计算出最好的序列吗?\n\n"}},{"title":"输入","value":{"format":"HTML","content":"输入包含几个迷宫的描述。每个迷宫描述以一行开头,其中包含两个整数 r 和 c (c\u0026lt;\u003d 20),代表迷宫的行数和列数。\n\u003c/br\u003e\n\u003c/br\u003e下面是r行,每行包含c个字符。每个角色描述迷宫的一个单元。充满岩石的单元格用“#”表示,空单元格用“。”表示。起始位置用“S”表示,框的起始位置用“B”表示,目标单元格用“T”表示。\n\u003c/br\u003e\n\u003c/br\u003e输入以r和c的两个0结束。\n"}},{"title":"输出","value":{"format":"HTML","content":"对于输入中的每个迷宫,首先打印迷宫的编号,如示例输出所示。然后,如果无法将盒子带到目标单元格,则打印“不可能”。\n\u003c/br\u003e\n\u003c/br\u003e否则,输出一个将 push 次数最小化的序列。如果有多个这样的序列,选择总移动(行走和推动)次数最少的序列。如果仍然有多于一个这样的序列,任何一个都是可以接受的。\n\u003c/br\u003e\n\u003c/br\u003e将序列打印为字符 N, S, E, W, N, S, E 和 W 的字符串,其中大写字母代表推,小写字母代表走,不同的字母代表北、南、东、西方向。\n\u003c/br\u003e\n\u003c/br\u003e在每个测试用例之后输出一个空行。\n"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 7\nSB....T\n1 7\nSB..#.T\n7 11\n###########\n#T##......#\n#.#.#..####\n#....B....#\n#.######..#\n#.....S...#\n###########\n8 4\n....\n.##.\n.#..\n.#..\n.#.B\n.##S\n....\n###T\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eMaze #1\nEEEEE\n\nMaze #2\nImpossible.\n\nMaze #3\neennwwWWWWeeeeeesswwwwwwwnNN\n\nMaze #4\nswwwnnnnnneeesssSSS\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}