{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"博格(Borg)是来自银河系三角洲区域的强大的增强型人形种族。博格集体是用来描述博格文明的集体意识的术语。每个博格个体都通过一个复杂的次空间网络与集体相连,确保每个成员都得到持续的监督和指导。\n\u003cbr\u003e\n\u003cbr\u003e你的任务是帮助博格(是的,真的)开发一个程序,帮助博格估算扫描迷宫以吸收藏在迷宫中的外星人的最小成本,通过向北、向西、向东和向南移动。棘手的是,搜索的开始是由一大群100多个个体进行的。每当一个外星人被同化,或者在搜索开始时,该群体可能会分裂成两个或更多个群体(但他们的意识仍然是集体的)。搜索迷宫的成本被定义为所有参与搜索的群体共同走过的总距离。也就是说,如果原始群体走了五步,然后分裂成两个群体,每个群体走了三步,总距离是11\u003d5+3+3。"}},{"title":"输入","value":{"format":"HTML","content":"在输入的第一行中,有一个整数N \u003c\u003d 50,表示输入中的测试用例数。每个测试用例以包含两个整数x,y的行开始,其中1 \u003c\u003d x,y \u003c\u003d 50。之后是y行,每行包含x个字符。对于每个字符,空格“ ”表示开放空间,井号“#”表示阻碍墙,大写字母“A”表示外星人,大写字母“S”表示搜索的开始。迷宫的周边始终是封闭的,即从“S”的坐标没有出路。迷宫中最多有100个外星人,并且每个外星人都是可到达的。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行,包含成功搜索迷宫并留下没有活着的外星人的最小成本。"}},{"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\u003e2\r\n6 5\r\n##### \r\n#A#A##\r\n# # A#\r\n#S ##\r\n##### \r\n7 7\r\n##### \r\n#AAA###\r\n# A#\r\n# S ###\r\n# #\r\n#AAA###\r\n##### \r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\r\n11\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}