{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"想象一下,你站在一个由方格单元组成的二维迷宫中,这些单元可能填满了岩石,也可能是空的。你可以向北、南、东或西移动一个单元格。这些移动被称为步行。\r\u003cbr\u003e其中一个空单元格包含一个箱子,可以通过站在箱子旁边然后朝着箱子的方向移动,将箱子移动到相邻的空单元格。这样的移动被称为推动。箱子只能通过推动来移动,这意味着如果你把它推到角落里,就再也无法把它推出来了。\r\u003cbr\u003e\r\u003cbr\u003e一个空单元格被标记为目标单元格。你的任务是通过一系列的步行和推动将箱子带到目标单元格。由于箱子很重,你希望尽量减少推动的次数。你能编写一个程序来找出最佳的移动顺序吗?\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/96148a04383d9fe2630a3ac772f12261?v\u003d1714286330\"\u003e\u003c/center\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个迷宫的描述。每个迷宫描述以包含两个整数 r 和 c(都小于等于 20)的行开始,表示迷宫的行数和列数。\r\u003cbr\u003e\r\u003cbr\u003e接下来是 r 行,每行包含 c 个字符。每个字符描述迷宫的一个单元格。用 `#\u0027 表示岩石填满的单元格,用 `.\u0027 表示空单元格。你的起始位置用 `S\u0027 表示,箱子的起始位置用 `B\u0027 表示,目标单元格用 `T\u0027 表示。\r\u003cbr\u003e\r\u003cbr\u003e输入以 r 和 c 均为零的两个零结束。\r\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于输入中的每个迷宫,首先按照示例输出显示迷宫的编号。然后,如果无法将箱子带到目标单元格,则打印“Impossible.”。\r\u003cbr\u003e\r\u003cbr\u003e否则,输出一个最小化推动次数的序列。如果存在多个这样的序列,请选择最小化总移动次数(步行和推动)的序列。如果仍然存在多个这样的序列,则任何一个都可以接受。\r\u003cbr\u003e\r\u003cbr\u003e将序列打印为字符 N、S、E、W、n、s、e 和 w 的字符串,其中大写字母表示推动,小写字母表示步行,不同的字母表示方向北、南、东和西。\r\u003cbr\u003e\r\u003cbr\u003e在每个测试用例后输出一个空白行。\r\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 7\r\nSB....T\r\n1 7\r\nSB..#.T\r\n7 11\r\n###########\r\n#T##......#\r\n#.#.#..####\r\n#....B....#\r\n#.######..#\r\n#.....S...#\r\n###########\r\n8 4\r\n....\r\n.##.\r\n.#..\r\n.#..\r\n.#.B\r\n.##S\r\n....\r\n###T\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eMaze #1\r\nEEEEE\r\n\r\nMaze #2\r\nImpossible.\r\n\r\nMaze #3\r\neennwwWWWWeeeeeesswwwwwwwnNN\r\n\r\nMaze #4\r\nswwwnnnnnneeesssSSS\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}