{"problem":{"name":"J. Complete the Square","description":{"content":"Complete the Square is a two-player game played on a grid of R rows, each containing C dots. In one turn, a player draws a vertical or a horizontal segment between two adjacent dots. This segment has","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10179J"},"statements":[{"statement_type":"Markdown","content":"Complete the Square is a two-player game played on a grid of R rows, each containing C dots.\n\nIn one turn, a player draws a vertical or a horizontal segment between two adjacent dots. This segment has to be new (not drawn before).\n\nA square is completed if its four sides are drawn. When a player completes a square, they write the first letter of their name in that square and receive one point. After completing a square, the same player has to draw another segment unless the grid is completed.\n\nAs shown in the image, in one turn, player B completed 5 squares and drew an extra segment. The numbers written in the squares are for clarifying the order in which the squares were completed. Note that it is possible that a player completes two squares at the same moment.\n\nGiven a state of the game, find the maximum number of squares you can complete in one turn.\n\nThe first line of input contains two integers R and C (2 ≤ R, C ≤ 1000), the number of rows and columns of the grid.\n\nEach of the following 2R - 1 rows contains 2C - 1 characters representing the state of the game. Since the letter in each square is irrelevant for solving the problem, a completed square will contain the lowercase English letter 'x'.\n\nA vertical segment is represented with a vertical bar '|', a horizontal segment is represented with a dash '-'. Dots are represented with the lowercase English letter 'o'. Edges that are not drawn or squares that are not completed will be represented with a dot '.'.\n\nIt is guaranteed that the input is valid in a way that every completed square is filled with an 'x', and every uncompleted square is filled with a dot '.'. No character will appear in an invalid place (for example, no '|' will appear in the place of a horizontal segment).\n\nThe given state of the game is not necessarily reachable through valid sequence of turns. However, consider it as an initial state for the game and solve the problem.\n\nPrint the maximum number of squares you can complete in one turn.\n\nThe first example represents the grid in the middle of the picture.\n\n## Input\n\nThe first line of input contains two integers R and C (2 ≤ R, C ≤ 1000), the number of rows and columns of the grid.Each of the following 2R - 1 rows contains 2C - 1 characters representing the state of the game. Since the letter in each square is irrelevant for solving the problem, a completed square will contain the lowercase English letter 'x'.A vertical segment is represented with a vertical bar '|', a horizontal segment is represented with a dash '-'. Dots are represented with the lowercase English letter 'o'. Edges that are not drawn or squares that are not completed will be represented with a dot '.'.It is guaranteed that the input is valid in a way that every completed square is filled with an 'x', and every uncompleted square is filled with a dot '.'. No character will appear in an invalid place (for example, no '|' will appear in the place of a horizontal segment).The given state of the game is not necessarily reachable through valid sequence of turns. However, consider it as an initial state for the game and solve the problem.\n\n## Output\n\nPrint the maximum number of squares you can complete in one turn.\n\n[samples]\n\n## Note\n\nThe first example represents the grid in the middle of the picture.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ R, C \\in \\mathbb{Z} $ with $ 2 \\leq R, C \\leq 1000 $ denote the number of rows and columns of dots in the grid.  \nLet $ G $ be a grid of size $ (2R - 1) \\times (2C - 1) $, where each cell is one of:  \n- `'o'`: a dot (vertex),  \n- `'|'`: a drawn vertical segment,  \n- `'-'`: a drawn horizontal segment,  \n- `'x'`: a completed square (all four sides drawn),  \n- `'.'`: an undrawn segment (edge not yet placed).  \n\nEach square in the grid corresponds to a cell at position $ (i, j) $ for $ i \\in \\{1, \\dots, R-1\\} $, $ j \\in \\{1, \\dots, C-1\\} $, bounded by:  \n- Top edge: $ G[2i-2][2j-1] $,  \n- Bottom edge: $ G[2i][2j-1] $,  \n- Left edge: $ G[2i-1][2j-2] $,  \n- Right edge: $ G[2i-1][2j] $.  \n\n**Constraints**  \n1. The grid is well-formed: all drawn segments and completed squares are in valid positions.  \n2. A square is completed iff all four of its edges are drawn (i.e., not `'.'`).  \n3. An edge is undrawn iff its cell is `'.'`.  \n4. A square is represented as `'x'` iff all four edges are drawn; otherwise, it is `'.'`.  \n\n**Objective**  \nFind the maximum number of squares that can be completed in a single turn by drawing exactly one new segment (either vertical or horizontal) between two adjacent dots.  \n\nLet $ S $ be the set of uncompleted squares (i.e., those with `'.'` in their center).  \nFor each square $ s \\in S $, define its **missing edges** as the set of its four sides that are currently `'.'`.  \nA square $ s $ can be completed in one turn iff it has **exactly one missing edge**.  \n\nLet $ M $ be the set of squares in $ S $ with exactly one missing edge.  \nEach such square corresponds to exactly one candidate edge to draw.  \n\nHowever, a single new segment may complete multiple squares simultaneously if it lies on the shared boundary between two adjacent squares.  \n\nLet $ E $ be the set of all undrawn edges (i.e., all `'.'` positions that are either horizontal or vertical segments).  \nFor each edge $ e \\in E $, let $ c(e) $ be the number of squares that would be completed if $ e $ were drawn.  \nThen $ c(e) \\in \\{0, 1, 2\\} $:  \n- $ c(e) = 0 $: $ e $ is adjacent to 0 or 1 squares, and drawing it completes none,  \n- $ c(e) = 1 $: $ e $ is adjacent to one square with all other three edges already drawn,  \n- $ c(e) = 2 $: $ e $ is an internal edge shared by two squares, both of which have all other three edges drawn.  \n\n**Objective**  \nCompute:  \n$$\n\\max_{e \\in E} c(e)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10179J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}