{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003eThe pasture contains a small, contiguous grove of trees that has no \u0027holes\u0027 in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She\u0027s just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn\u0027t think you could pass \u0027through\u0027 the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take. Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 \u0026lt;\u003d R \u0026lt;\u003d 50, 1 \u0026lt;\u003d C \u0026lt;\u003d 50). Here\u0027s a typical example where \u0027.\u0027 is pasture (which Bessie may traverse), \u0027X\u0027 is the grove of trees, \u0027*\u0027 represents Bessie\u0027s start and end position, and \u0027+\u0027 marks one shortest path she can walk to circumnavigate the grove (i.e., the answer): ...+... ..+X+.. .+XXX+. ..+XXX+ ..+X..+ ...+++* The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she\u0027s starting \u0027outside\u0027 the grove instead of in a sort of \u0027harbor\u0027 that could complicate finding the best path.\n\u003cbr\u003e \n\u003cbr\u003e 牧场里有一片树林,林子里没有坑.贝茜很想知道,最少需要多少步能围绕树林走一圈,最后回到起点.她能上下左右走,也能走对角线格子.牧场被分成R行C列(1≤R≤50,1≤C≤50).下面是一张样例的地图,其中“.”表示贝茜可以走的空地,\u0026nbsp; “X”表示树林,\u0026nbsp; “*”表示起点.而贝茜走的最近的路已经特别地用“+”表示出来.\n\u003cbr\u003e 题目保证,最短的路径一定可以找到.\n\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"* Line 1: Two space-separated integers: R and C\n\u003cbr\u003e * Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).\n\u003cbr\u003e 第1行输入R和C,接下来R行C列表示一张地图.地图中的符号如题干所述.\n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"* Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.\n\u003cbr\u003e 输出最少的步数.\n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e6 7\r\n.......\r\n...X...\r\n..XXX..\r\n...XXX.\r\n...X...\r\n......*\u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eSample Output\u003c/h2\u003e\n\u003cpre class\u003dcontent\u003e\u003cspan class\u003dsampledata\u003e13\u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eHINT\u003c/h2\u003e\n\u003cdiv class\u003dcontent\u003e\u003cp\u003e\u003c/p\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e13\u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eHINT\u003c/h2\u003e\n\u003cdiv class\u003dcontent\u003e\u003cp\u003e\u003c/p\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e"}}]}