{"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\"\u003e昨晚,小二月做了一个可怕的噩梦。他梦见他和他的女朋友被困在一个大迷宫里。更可怕的是,迷宫里有两个鬼魂。它们会杀人。现在小二月想知道他是否能在鬼魂找到他们之前找到他的女朋友。\u003cbr\u003e你可以假设小二月和他的女朋友可以向四个方向移动。每秒钟,小二月可以移动3步,他的女朋友可以移动1步。鬼魂很邪恶,它们每秒钟会分裂成几部分,占据距离它们2步以内的格子,直到占据整个迷宫。你可以假设在每一秒钟,鬼魂首先分裂,然后小二月和他的女朋友开始移动,如果小二月或者他的女朋友到达一个有鬼魂的格子,他们就会死去。\u003cbr\u003e注意:新的鬼魂也可以像原来的鬼魂一样分裂。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入以一个整数T开始,表示测试用例的数量。\u003cbr\u003e每个测试用例以包含两个整数n和m的行开始,表示迷宫的大小。(1\u0026lt;n, m\u0026lt;800)\u003cbr\u003e接下来的n行描述了迷宫。每行包含m个字符。字符可能是:\u003cbr\u003e‘.’ 表示一个空地,所有人都可以走。\u003cbr\u003e‘X’ 表示一堵墙,只有人不能走。\u003cbr\u003e‘M’ 表示小二月\u003cbr\u003e‘G’ 表示女朋友。\u003cbr\u003e‘Z’ 表示鬼魂。\u003cbr\u003e保证迷宫中恰好包含一个字母M,一个字母G和两个字母Z。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"在一行中输出一个整数S,表示小二月和他的女朋友将在最短时间S内相遇,如果他们成功相遇,则输出-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\u003e3\r\n5 6\r\nXXXXXX\r\nXZ..ZX\r\nXXXXXX\r\nM.G...\r\n......\r\n5 6\r\nXXXXXX\r\nXZZ..X\r\nXXXXXX\r\nM.....\r\n..G...\r\n\r\n10 10\r\n..........\r\n..X.......\r\n..M.X...X.\r\nX.........\r\n.X..X.X.X.\r\n.........X\r\n..XX....X.\r\nX....G...X\r\n...ZX.X...\r\n...Z..X..X\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}