{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e pre { text-align:left; font-family: \"Courier New\", Courier, monospace; font-size: 16px; white-space: pre; line-height:20px; text-indent: 0px; }\u003c/style\u003e\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003e胖兄弟和迷宫正在一个 N*M 的棋盘上玩一种特殊的(变态的)游戏。一开始,棋盘上的每个格子都是草或者空的,然后他们开始点燃所有的草。首先他们选择两个格子,这两个格子是草,然后点燃它们。众所周知,火可以在草之间蔓延。如果格子 (x, y) 在时间 t 被点燃,与这个格子相邻的格子将在时间 t+1 被点燃,相邻指的是格子 (x+1, y), (x-1, y), (x, y+1), (x, y-1)。这个过程在没有新的格子被点燃时结束。如果所有的草都被点燃了,胖兄弟和迷宫将站在棋盘的中间玩一个更特殊的(变态的)游戏。(也许是上一个问题中解密的 OOXX 游戏,谁知道呢。)\u003c/p\u003e\n \u003cp\u003e你可以假设棋盘上的草永远不会烧完,空的格子永远不会被点燃。\u003c/p\u003e\n \u003cp\u003e注意,他们选择的两个格子可以是相同的。\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003e第一行是一个整数 T,表示测试用例的数量。\u003c/p\u003e\n \u003cp\u003e接下来是 T 个测试用例,每个用例包含两个整数 N 和 M,表示棋盘的大小。然后是 N 行,每行包含 M 个字符表示棋盘。“#” 表示草。你可以假设棋盘上至少有一个格子是草。\u003c/p\u003e\n \u003cp\u003e1 \u0026lt;\u003d T \u0026lt;\u003d100, 1 \u0026lt;\u003d n \u0026lt;\u003d10, 1 \u0026lt;\u003d m \u0026lt;\u003d10\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cdiv class\u003d\"pro_desc\"\u003e\n \u003cp\u003e对于每个测试用例,首先输出用例编号,如果他们可以玩更特殊的(变态的)游戏(点燃所有的草),输出他们点燃后需要等待的最短时间,否则输出 -1。更多细节请参见样例输入和输出。\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"样例输入","value":{"format":"HTML","content":"\u003cpre\u003e4\r\n3 3\r\n.#.\r\n###\r\n.#.\r\n3 3\r\n.#.\r\n#.#\r\n.#.\r\n3 3\r\n...\r\n#.#\r\n...\r\n3 3\r\n###\r\n..#\r\n#.#\u003c/pre\u003e"}},{"title":"样例输出","value":{"format":"HTML","content":"\u003cpre\u003eCase 1: 1\r\nCase 2: -1\r\nCase 3: 0\r\nCase 4: 2\u003c/pre\u003e"}}]}