{"raw_statement":[{"iden":"statement","content":"You are given a board of $R$ rows and $C$ columns where each cell is either a dry land ('_#_') or an icy land ('_._'). You can move to either one of the four directions (north, south, east, or west) in the board.\n\nYou can walk or standstill on any dry land without any problem; however, an icy land is very slippery. If you stand at cell $(r, c)$ and decide to move on a particular direction, then you will move on that direction continuously until you reach a dry land or the border of the board.\n\nFor example, consider the following board of $6$ rows and $7$ column.\n\nSupposed your initial position is at cell $(3, 7)$ and your moves are west, west, west, south, east, north, west, and west, respectively. Then your positions are $(3, 7)$ $arrow.r$ $(3, 4)$ $arrow.r$ $(3, 3)$ $arrow.r$ $(3, 1)$ $arrow.r$ $(6, 1)$ $arrow.r$ $(6, 2)$ $arrow.r$ $(2, 2)$ $arrow.r$ $(2, 1)$ $arrow.r$ $(2, 1)$, thus, visiting $8$ different cells. Note that cell $(2, 1)$ is visited twice. Cells in which you only passed through are also not considered as visited, e.g., in the example above, if you move south from $(3, 1)$, then you will pass through $(4, 1)$ and $(5, 1)$, and arrive at $(6, 1)$; thus, $(4, 1)$ and $(5, 1)$ are not considered as visited from that particular move, only $(3, 1)$ and $(6, 1)$ are.\n\nYou are allowed to change any icy land into a dry land, and your goal is to make sure that you can always visit *all* the cells in the board *regardless* of your initial starting position; in other words, you do not know your starting position yet, but given the board, you want to make sure that you can achieve your goal. What is the minimum number of cells you need to change to ensure that your goal can be achieved?\n\nInput begins with a line containing two integers: $R$ $C$ ($1 <= R, C <= 500$) representing the number of rows and columns of the board, respectively. The next $R$ lines, each contains $C$ characters representing the given board. Each character is either '_#_' which represents a dry land or '_._' which represents an icy land.\n\nOutput contains an integer in a line representing the minimum number of cells you need to change to ensure that you can visit all the cells in the board regardless of your initial starting position.\n\n_Explanation for the sample input/output_\n\nWe only need to change cell $(3, 3)$.\n\nLet 'N' be north, 'S' be south, 'W' be west, and 'E' be east.\n\n"},{"iden":"input","content":"Input begins with a line containing two integers: $R$ $C$ ($1 <= R, C <= 500$) representing the number of rows and columns of the board, respectively. The next $R$ lines, each contains $C$ characters representing the given board. Each character is either '_#_' which represents a dry land or '_._' which represents an icy land."},{"iden":"output","content":"Output contains an integer in a line representing the minimum number of cells you need to change to ensure that you can visit all the cells in the board regardless of your initial starting position."},{"iden":"note","content":"_Explanation for the sample input/output_We only need to change cell $(3, 3)$.   ....   .###   ###.   ###.Let 'N' be north, 'S' be south, 'W' be west, and 'E' be east.  If you start at cell $(1, 1)$, then the movement \"SSENNWENSESSEWNENWNE\" will visit all the cells. The corresponding positions are: $(1, 1)$ $arrow.r$ $(3, 1)$ $arrow.r$ $(4, 1)$ $arrow.r$ $(4, 2)$ $arrow.r$ $(3, 2)$ $arrow.r$ $(2, 2)$ $arrow.r$ $(2, 1)$ $arrow.r$ $(2, 2)$ $arrow.r$ $(1, 2)$ $arrow.r$ $(2, 2)$ $arrow.r$ $(2, 3)$ $arrow.r$ $(3, 3)$ $arrow.r$ $(4, 3)$ $arrow.r$ $(4, 4)$ $arrow.r$ $(4, 3)$ $arrow.r$ $(3, 3)$ $arrow.r$ $(3, 4)$ $arrow.r$ $(2, 4)$ $arrow.r$ $(2, 3)$ $arrow.r$ $(1, 3)$ $arrow.r$ $(1, 4)$.  If you start at cell $(1, 2)$, then the movement \"W\" followed by the movement in the first example above (\"SSENNWENSESSEWNENWNE\") will visit all the cells. The corresponding positions are: $(1, 2)$ $arrow.r$ $(1, 1)$ $arrow.r$ $\\\\dots$  If you start at cell $(1, 3)$, then the movement \"W\" followed by the movement in the first example above will visit all the cells. The corresponding positions are: $(1, 3)$ $arrow.r$ $(1, 1)$ $arrow.r$ $\\\\dots$  $\\\\\\\\cdots$  If you start at cell $(4, 3)$, then the movement \"NNNW\" followed by the movement in the first example above will visit all the cells. The corresponding positions are: $(4, 3)$ $arrow.r$ $(3, 3)$ $arrow.r$ $(2, 3)$ $arrow.r$ $(1, 3)$ $arrow.r$ $(1, 1)$ $arrow.r$ $\\\\dots$  If you start at cell $(4, 4)$, then the movement \"NNW\" followed by the movement in the first example above will visit all the cells. The corresponding positions are: $(4, 4)$ $arrow.r$ $(2, 4)$ $arrow.r$ $(1, 4)$ $arrow.r$ $(1, 1)$ $arrow.r$ $\\\\dots$ "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ r, c \\in \\mathbb{Z} $ denote the number of rows and columns of the grid.  \n- Let $ B = (b_1, \\dots, b_c) \\in \\mathbb{Z}_{\\geq 0}^c $, where $ b_i $ is the number of balls dropped into column $ i $.  \n- Let $ S = (s_1, \\dots, s_c) \\in \\mathbb{Z}_{\\geq 0}^c $, where $ s_i $ is the score per ball in bucket $ i $.  \n- Let $ G = (g_{i,j})_{r \\times c} $ be the initial grid, where each $ g_{i,j} \\in \\{ \\text{.}, \\backslash, / \\} $.  \n\nCells with $ g_{i,j} = \\text{.} $ are fixed.  \nCells with $ g_{i,j} \\in \\{ \\backslash, / \\} $ may be changed to any of $ \\{ \\text{.}, \\backslash, / \\} $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 5300 $  \n2. $ 1 \\leq r, c \\leq 500 $  \n3. $ \\sum_{\\text{test cases}} r \\times c \\leq 4 \\times 10^6 $  \n4. $ 0 \\leq b_i, s_i \\leq 10^8 $  \n5. **No two adjacent cells in the same row may satisfy**: left cell is $ \\backslash $ and right cell is $ / $.  \n\n**Objective**  \nMaximize total score:  \n$$\n\\sum_{j=1}^{c} s_j \\cdot (\\text{number of balls from column } j \\text{ that reach bucket } j)\n$$  \nby choosing, for each variable cell $ (i,j) $, a symbol in $ \\{ \\text{.}, \\backslash, / \\} $, such that:  \n- The path of each ball dropped in column $ j $ follows grid directions ($ \\backslash $: down-right, $ / $: down-left, $ . $: down),  \n- No ball leaves the grid boundaries (i.e., if a ball moves left from column 1 or right from column $ c $, it scores 0),  \n- The adjacency constraint is satisfied: $ \\forall i \\in \\{1,\\dots,r\\}, \\forall j \\in \\{1,\\dots,c-1\\} $, it is not allowed that $ g_{i,j} = \\backslash $ and $ g_{i,j+1} = / $.  \n\nFind the maximum achievable total score.","simple_statement":"You have a grid of r rows and c columns. Each cell is '.', '\\', or '/'. You can change any '\\' or '/' to any of the three types, but '.' cannot be changed.\n\nBalls are dropped into each column — bi balls in column i. Each ball falls straight down until it hits a slanted cell ('\\' or '/'), which redirects it left or right. Eventually, it lands in a bucket below a column and adds si to your score.\n\nYou cannot have a '\\' directly to the left of a '/' in the same row.\n\nGoal: Maximize total score by changing slanted cells optimally.","has_page_source":false}