{"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\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/690f2f6afaaf09045a68abd275037d93?v\u003d1721499436\"\u003e\u003c/center\u003e \u003cbr\u003eA defensive wall is a fortification used to protect a city or settlement from potential aggressors. From ancient to modern times, they were used to enclose settlements.\u003cbr\u003eGenerally, these are referred to as city walls or town walls.\u003cbr\u003eEven though, our ancestors decided to build a Great Wall to protect the northern borders of the Chinese Empire against invasion by various nomadic groups.\u003cbr\u003eThe map is given as an rectangle area of size N × M. Each grid is an empty area, a city or an enemy. The Great Wall is a simple polygon build alone the edge of the grids, enclosing all the cities and keeping all the enemies out.\u003cbr\u003eThe Great Wall is not easy to build, so we should make the Great Wall as short as possible. Now it is your job to calculate the length of the shortest Great Wall so that it can protect all the cities from the enemies.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T(1 \u0026lt;\u003d T\u0026lt;\u003d 50), indicating the number of test cases.\u003cbr\u003eEach test case contains several lines.\u003cbr\u003eThe first line contains two integer H,W(1 \u0026lt;\u003d H,W \u0026lt;\u003d 8), indicating the number of rows and columns of the map.\u003cbr\u003eThe followingH lines containsW chars, indicating the map. \u0027o\u0027 represents a city, \u0027.\u0027 represents a empty area and \u0027x\u0027 represents an enemy.\u003cbr\u003eYou can assume that there will be at least one city on the map."}},{"title":"Output","value":{"format":"HTML","content":"For each test case in the input, print one line: \"Case #X: Y\", where X is the test case number (starting with 1) and Y is the length of the shortest Great Wall (-1 if impossible)."}},{"title":"Sample","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\n3 3\r\n.o.\r\n.x.\r\no.o\r\n4 4\r\n....\r\n.ox.\r\n.xo.\r\n....\r\n5 5\r\n.ooo.\r\n.x...\r\n..xoo\r\nx.xoo\r\n.ox.x\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 14\r\nCase #2: -1\r\nCase #3: 28\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eA simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments.\u003cbr\u003eThe solution for the first test case in sample is shown in Figure 1.\u003cbr\u003eThere is no solution for the second test case because no matter how you build the Great Wall, it will always intersects with itself. (Figure 2).\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/598d3325d61d4f386f4c7b221bb2ba0e?v\u003d1721499436\"\u003e\u003c/center\u003e \u003cbr\u003e"}}]}