{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:40.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/ebb4f35f802dceca4c197ebabab9c7d2?v\u003d1715827830\" alt\u003d\"/problems/dotsboxes/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eAlice and Bob are playing Dots and Boxes. The game is played\n on an \u003cspan class\u003d\"tex2jax_process\"\u003e$N\\times N$\u003c/span\u003e square\n lattice of dots, and they alternate drawing a line segment\n between horizontally or vertically adjacent dots that haven’t\n been connected before. Every time a unit square is formed by\n four line segments, the player who put down the last segment\n scores one point for that square. The game ends when the square\n lattice has been completely filled with line segments, and\n whoever scored the most points wins.\u003c/p\u003e\n\n \u003cp\u003eAlice and Bob aren’t really in a competitive mood today, so\n they’ve just been playing for fun. Hence they aren’t following\n any specific game strategy, and, in particular, even if it’s\n possible to make a move that scores a point or is clearly\n superior in some way, they won’t necessarily make that move.\n But now they’ve been playing for a while and neither of them\n has scored a single point. If neither of them scores a point\n pretty soon, they may get bored. Given the current state of the\n game, how many moves could be made, in the worst case, before\n either Alice or Bob is guaranteed to have scored a point?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eInput starts with a line containing an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2\n \\leq N \\leq 80$\u003c/span\u003e), the size of the square lattice. Then\n follows an ASCII representation of the current state of the\n game, \u003cspan class\u003d\"tex2jax_process\"\u003e$2N-1$\u003c/span\u003e rows high and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2N-1$\u003c/span\u003e columns wide,\n listed in row-major order. There are cells of four types\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq i,j \\leq N$\u003c/span\u003e):\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eCell \u003cspan class\u003d\"tex2jax_process\"\u003e$(2i-1,2j-1)$\u003c/span\u003e\n is ‘\u003ctt class\u003d\"ttfamily\"\u003e*\u003c/tt\u003e’, representing dot\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(i,j)$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eCell \u003cspan class\u003d\"tex2jax_process\"\u003e$(2i,2j)$\u003c/span\u003e is\n ‘\u003ctt class\u003d\"ttfamily\"\u003e.\u003c/tt\u003e’, representing empty\n space.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eCell \u003cspan class\u003d\"tex2jax_process\"\u003e$(2i,2j-1)$\u003c/span\u003e is\n ‘\u003ctt class\u003d\"ttfamily\"\u003e|\u003c/tt\u003e’ if dots \u003cspan class\u003d\"tex2jax_process\"\u003e$(i,j)$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$(i+1,j)$\u003c/span\u003e have been connected by a\n line segment, and ‘\u003ctt class\u003d\"ttfamily\"\u003e.\u003c/tt\u003e’\n otherwise.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eCell \u003cspan class\u003d\"tex2jax_process\"\u003e$(2i-1,2j)$\u003c/span\u003e is\n ‘\u003ctt class\u003d\"ttfamily\"\u003e-\u003c/tt\u003e’ if dots \u003cspan class\u003d\"tex2jax_process\"\u003e$(i,j)$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$(i,j+1)$\u003c/span\u003e have been connected by a\n line segment, and ‘\u003ctt class\u003d\"ttfamily\"\u003e.\u003c/tt\u003e’\n otherwise.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eIt is guaranteed that no player has scored a point, meaning\n that no unit squares have been formed.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput the number of moves that can be made, in the worst\n case, before either Alice or Bob is guaranteed to have scored a\n point.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\n*-*.*\n|.|.|\n*.*-*\n|...|\n*.*.*\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e2\n*.*\n...\n*.*\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e4\n*-*-*.*\n|...|..\n*-*-*-*\n|.....|\n*.*.*-*\n|.....|\n*-*-*-*\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}