{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThere is a rectangular area containing \u003ci\u003en\u003c/i\u003e × \u003ci\u003em\u003c/i\u003e cells. Two cells are marked with “2”, and another two with “3”. Some cells are occupied by obstacles. You should connect the two “2”s and also the two “3”s with non-intersecting lines. Lines can run only vertically or horizontally connecting centers of cells without obstacles.\u003c/p\u003e\u003cp\u003eLines cannot run on a cell with an obstacle. Only one line can run on a cell at most once. Hence, a line cannot intersect with the other line, nor with itself. Under these constraints, the total length of the two lines should be minimized. The length of a line is defined as the number of cell borders it passes. In particular, a line connecting cells sharing their border has length 1.\u003c/p\u003e\u003cp\u003eFig. 1(a) shows an example setting. Fig. 1(b) shows two lines satisfying the constraints above with minimum total length 18.\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/d530c4129f7ef014e27e037adffe12cb?v\u003d1714484970\"\u003e\u003c/div\u003e\u003cp align\u003d\"center\"\u003eFigure 1: An example of setting and its solution\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe input consists of multiple datasets, each in the following format.\u003c/p\u003e\u003cblockquote\u003e\u003ctable border\u003d\"0\" width\u003d\"50\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd width\u003d\"50%\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/td\u003e\u003ctd width\u003d\"50%\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\"\u003erow\u003csub\u003e1\u003c/sub\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\"\u003e…\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\"\u003erow\u003ci\u003e\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/blockquote\u003e\u003cp\u003e\u003ci\u003en\u003c/i\u003e is the number of rows which satisfies 2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 9. m is the number of columns which satisfies 2 ≤ \u003ci\u003em\u003c/i\u003e ≤ 9. Each row\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e is a sequence of \u003ci\u003em\u003c/i\u003e digits separated by a space. The digits mean the following.\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ccode\u003e0:\u003c/code\u003e Empty\u003c/p\u003e\u003cp\u003e\u003ccode\u003e1:\u003c/code\u003e Occupied by an obstacle\u003c/p\u003e\u003cp\u003e\u003ccode\u003e2:\u003c/code\u003e Marked with “2”\u003c/p\u003e\u003cp\u003e\u003ccode\u003e3:\u003c/code\u003e Marked with “3”\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003eThe end of the input is indicated with a line containing two zeros separated by a space.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eFor each dataset, one line containing the minimum total length of the two lines should be output. If there is no pair of lines satisfying the requirement, answer “\u003ccode\u003e0\u003c/code\u003e” instead. No other characters should be contained in the output.\u003c/p\u003e\u003c/span\u003e"}},{"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\u003e5 5\r\n0 0 0 0 0\r\n0 0 0 3 0\r\n2 0 2 0 0\r\n1 0 1 1 1\r\n0 0 0 0 3\r\n2 3\r\n2 2 0\r\n0 3 3\r\n6 5\r\n2 0 0 0 0\r\n0 3 0 0 0\r\n0 0 0 0 0\r\n1 1 1 0 0\r\n0 0 0 0 0\r\n0 0 2 3 0\r\n5 9\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 3 0 0 0 0\r\n0 2 0 0 0 0 0 2 0\r\n0 0 0 0 3 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n9 9\r\n3 0 0 0 0 0 0 0 2\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n2 0 0 0 0 0 0 0 3\r\n9 9\r\n0 0 0 1 0 0 0 0 0\r\n0 2 0 1 0 0 0 0 3\r\n0 0 0 1 0 0 0 0 2\r\n0 0 0 1 0 0 0 0 3\r\n0 0 0 1 1 1 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n9 9\r\n0 0 0 0 0 0 0 0 0\r\n0 3 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 0 0 0\r\n0 0 0 0 0 0 2 3 2\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18\r\n2\r\n17\r\n12\r\n0\r\n52\r\n43\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}