{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eRompire是一个机器人王国,许多机器人在那里和平地生活着。但是有一天,Rompire的国王被人类俘虏了。他的思维电路被人类改变,从而成为了一个暴君。所有反抗他的人都被关进了监狱,包括我们聪明的Micheal#1。现在是时候逃跑了,但Micheal#1需要一个最佳计划,他联系了你,他的人类朋友,寻求帮助。\u003cbr\u003e监狱区域是一个包含n×m个小网格的矩形,每个网格可能是以下之一:\u003cbr\u003e1) 空地区域,用大写字母\u0027S\u0027表示。\u003cbr\u003e2) Micheal#1的起始位置,用大写字母\u0027F\u0027表示。\u003cbr\u003e3) 能量池,用大写字母\u0027G\u0027表示。当进入能量池时,Micheal#1可以用它来充电,但只能充一次。充电后,Micheal#1的电池将变为满格,而能量池将变为空地区域。当然,可以不使用能量池而直接通过。\u003cbr\u003e4) 激光传感器,用大写字母\u0027D\u0027表示。由于它非常敏感,Micheal#1不能踏入带有激光传感器的网格。\u003cbr\u003e5) 电源开关,用大写字母\u0027Y\u0027表示。一旦Micheal#1踏入带有电源开关的网格,他将立即关闭它。\u003cbr\u003e\u003cbr\u003e为了逃离监狱,Micheal#1需要关闭所有电源开关以停止屋顶上的电网,然后他就可以飞走了。移动到相邻的网格(直接上、下、左或右)将消耗1单位能量,只有移动操作会消耗能量。当然,当Micheal#1的电池没有能量时,他无法移动。\u003cbr\u003e\u003cbr\u003e电池越大,能保存的能量就越多。但是更大的电池意味着更重的重量,被重量传感器发现的可能性更高。因此,Micheal#1需要尽可能地减小他的电池,同时仍然足够大以容纳他所需的所有能量。假设电池的大小等于电池中可以保存的最大能量单位,并且Micheal#1在开始时是充满电的,请告诉他逃跑所需的最小电池大小。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个测试用例,以0 0结束。对于每个测试用例,第一行包含两个整数n和m,表示监狱的大小。接下来的n行包含每行m个大写字母,表示监狱的描述。你可以假设1≤n,m≤15,并且能量池和电源开关的总数小于15。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一个整数,表示Micheal#1所需的最小电池大小。如果Micheal#1无法逃跑,则输出-1。"}},{"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\u003e5 5\r\nGDDSS\r\nSSSFS\r\nSYGYS\r\nSGSYS\r\nSSYSS\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}