{"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 \u003cp\u003eRemember the busy boards for toddlers that have an array of\n holes into which to hammer pegs of various shapes? There’s a\n new, electronic version. The board consists of a 2D grid of\n pegs. Each peg on the board can be either \u003ci class\u003d\"itshape\"\u003eup\u003c/i\u003e or \u003ci class\u003d\"itshape\"\u003edown\u003c/i\u003e, but not both\n simultaneously. You can pick any peg that is currently up, and\n “hammer” it down. This will push that peg down, and also raise\n all of the other pegs in its row, and its column, regardless of\n their current state. You cannot “hammer” a peg that is down\n (well, maybe you can, but it will have no effect). Those poor\n kids will never get all the pegs down at one time!\u003c/p\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/90ff3450e3d11f645df93b7ef506cbcc?v\u003d1715974424\" alt\u003d\"\\includegraphics[width\u003d0.3\\textwidth ]{hammering.jpg}\" style\u003d\"width:30.00%\"\u003e\n \u003c/center\u003e\n \u003cp\u003eThis example shows what happens when the top right peg is\n “hammered.” (\u003cspan class\u003d\"tex2jax_process\"\u003e$\\circ \u003d$\u003c/span\u003e up,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$\\bullet \u003d$\u003c/span\u003e down)\u003c/p\u003e\n \u003cp\u003eA substitute teacher wants to challenge her class. She uses\n the “Teacher Mode” to set up the board in a particular\n configuration, and then asks her students to see if they can\n get the board to a second configuration by hammering some\n (perhaps none) of the pegs.\u003c/p\u003e\n \u003cp\u003eThat may be too tough of a problem for toddlers, but maybe\n you can handle it.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eEach test case will begin with a line with two\n space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\\! \\le \\! r,c\\! \\le \\! 1\\, 000$\u003c/span\u003e),\n which are the dimensions of the board.\u003c/p\u003e\n \u003cp\u003eEach of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e\n lines will have exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e characters, consisting only of\n capital ‘\u003cb class\u003d\"bf\"\u003e\u003ctt class\u003d\"ttfamily\"\u003eO\u003c/tt\u003e\u003c/b\u003e’\n (representing a peg that is up), capital ‘\u003cb class\u003d\"bf\"\u003e\u003ctt class\u003d\"ttfamily\"\u003eX\u003c/tt\u003e\u003c/b\u003e’ (representing a peg that\n is down), and no spaces or other characters. This is the\n starting configuration.\u003c/p\u003e\n \u003cp\u003eFollowing this, each of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e lines will have exactly\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e characters, consisting\n only of capital ‘\u003cb class\u003d\"bf\"\u003e\u003ctt class\u003d\"ttfamily\"\u003eO\u003c/tt\u003e\u003c/b\u003e’\n (representing a peg that is up), capital ‘\u003cb class\u003d\"bf\"\u003e\u003ctt class\u003d\"ttfamily\"\u003eX\u003c/tt\u003e\u003c/b\u003e’ (representing a peg that\n is down), and no spaces or other characters. This is the target\n configuration.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput a single integer, \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e if it is possible to reach the\n target configuration from the starting configuration, and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e if it is\n impossible.\u003c/p\u003e\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\u003e4 2\nXO\nOX\nXO\nOX\nOX\nOO\nXO\nOO\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\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 4\nXXXX\nXXXX\nXOOO\nOOOO\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}