{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e蜂巢是蜜蜂建造的一堆蜂蜡单元,可以被描述为欧几里得平面的正规镶嵌,其中每个内部顶点相交的是三个六边形。六边形的内角是$$$120$$$度,所以一个点上的三个六边形构成了$$$360$$$度。下图显示了一个完整的蜂巢,有$$$3$$$行和$$$4$$$列。\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f6f960b1d3d570555f01f75a4e8e1f98?v\u003d1705064439\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e在这里我们保证第二列中的第一个单元格总是位于第一列中第一个单元格的右下方,如上所示。一个一般的蜂巢可能会在一个完整的蜂巢的基础上失去一些相邻单元格之间的墙壁,但蜂巢仍然是封闭的。可能的情况如下图所示。\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/b4adf4a68a96ee456978d224a0a4ff4c?v\u003d1705064439\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e汉密尔顿是一只生活在一般蜂巢中的勇敢的蜜蜂。现在他想要从起点移动到指定的目的地。下图展示了在一个$$$3 \\times 4$$$行蜂巢中从第$$$1$$$列的第$$$2$$$个单元格到第$$$1$$$列的第$$$4$$$个单元格的可行路径。\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/46ec35a0d156f88b719bc16b33b8a8d7?v\u003d1705064439\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e请帮助他找到从指定起点到目的地的可行路径所需经过的最少单元格数(包括起点和目的地)。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入包含多个测试用例,第一行包含一个正整数$$$T$$$,表示测试用例的数量,最多为$$$10^4$$$。\u003c/p\u003e\u003cp\u003e对于每个测试用例,第一行包含两个整数$$$r$$$和$$$c$$$,表示蜂巢的行数和列数,其中$$$2 \\leq r, c \\leq 10^3$$$。\u003c/p\u003e\u003cp\u003e接下来的$$$(4 r + 3)$$$行描述了给定蜂巢的全部内容,每行包含最多$$$(6 c + 3)$$$个字符。奇数行包含以加号 (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e\") 表示的网格顶点和零个或多个水平边,而偶数行包含两个或多个对角边。具体来说,一个单元格由$$$6$$$个顶点和最多$$$6$$$条边描述。它的上边界或下边界用三个连续的减号 (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-\u003c/span\u003e\") 表示。如果存在的话,它的每一条对角边都是一个单独的正斜杠 (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e/\u003c/span\u003e\") 或一个单独的反斜杠 (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e\\\u003c/span\u003e\") 字符。所有边的字符都将被放置在相应的顶点之间。在起始单元格的中心(或者目的地),一个大写字母 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eS\u003c/span\u003e\"(或者大写字母 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e\")作为特殊字符用来指示特殊单元格。所有其他字符都将是空格字符。请注意,如果任何输入行可能包含尾随空格,那么这些空格将被省略。\u003c/p\u003e\u003cp\u003e我们保证所有最外层的墙壁都存在,所以给定的蜂巢是封闭的,并且在给定的蜂巢中只有一个 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eS\u003c/span\u003e\" 和一个 \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e\"。此外,在所有测试用例中,$$$r \\cdot c$$$的总和最多为$$$2 \\times 10^6$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,输出一行,包含汉密尔顿从起始单元格 (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003eS\u003c/span\u003e\") 移动到目的地 (\"\u003cspan class\u003d\"tex-font-style-tt\"\u003eT\u003c/span\u003e\") 所需经过的最少单元格数,包括起始单元格和目的地。如果不存在可行路径,则输出\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e。\u003c/p\u003e"}},{"title":"示例 1","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\n3 4\n +---+ +---+\n / \\ / \\\n+ +---+ +---+\n \\ \\ / \\\n + + S +---+ T +\n / \\ / /\n+ +---+ + +\n \\ \\ / \\\n +---+ +---+ +\n / /\n+ +---+ + +\n \\ / \\\n +---+ +---+ +\n \\ / \\ /\n +---+ +---+\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}