{"raw_statement":[{"iden":"problem statement","content":"There is a grid with $N$ rows and $N$ columns. Let $(i, j)$ $(1 \\leq i \\leq N, 1 \\leq j \\leq N)$ denote the cell at the $i$\\-th row from the top and the $j$\\-th column from the left. Each cell is initially painted red or blue, with cell $(i, j)$ being red if $c_{i,j}=$`R` and blue if $c_{i,j}=$`B`. You want to change the colors of some cells to purple so that the following two conditions are simultaneously satisfied:\n\n> **Condition 1**: You can move from cell $(1, 1)$ to cell $(N, N)$ by only passing through cells that are red or purple.  \n> **Condition 2**: You can move from cell $(1, N)$ to cell $(N, 1)$ by only passing through cells that are blue or purple.\n\nHere, \"**You can move**\" means that you can reach the destination from the starting point by repeatedly moving to a horizontally or vertically adjacent cell of the relevant colors.\nWhat is the minimum number of cells that must be changed to purple to satisfy these conditions?"},{"iden":"constraints","content":"*   $3 \\leq N \\leq 500$\n*   Each $c_{i,j}$ is `R` or `B`.\n*   $c_{1,1}$ and $c_{N,N}$ are `R`.\n*   $c_{1,N}$ and $c_{N,1}$ are `B`.\n*   $N$ is an integer."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$c_{1,1}$$c_{1,2}$$\\cdots$$c_{1,N}$\n$c_{2,1}$$c_{2,2}$$\\cdots$$c_{2,N}$\n$\\vdots$\n$c_{N,1}$$c_{N,2}$$\\cdots$$c_{N,N}$"},{"iden":"sample input 1","content":"5\nRBRBB\nRBRRR\nRRRBR\nRBBRB\nBBRBR"},{"iden":"sample output 1","content":"3\n\nAs shown in the figure below, changing cells $(1, 3), (3, 2), (4, 5)$ to purple satisfies the conditions.\n![image](https://img.atcoder.jp/arc177/7f2b28ec79263ffd4381a20038c7daef.png)"},{"iden":"sample input 2","content":"5\nRBBBB\nBBBBB\nBBBBB\nBBBBB\nBBBBR"},{"iden":"sample output 2","content":"7\n\nAs shown in the figure below, changing cells $(1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 5)$ to purple satisfies the conditions.\n![image](https://img.atcoder.jp/arc177/0f50b092f2abc545bdbfb7b8cfa66bdc.png)"},{"iden":"sample input 3","content":"10\nRRBBBBBBBB\nBRRBBBBBBB\nBBRRBBBBBB\nBBBRRBBBBB\nBBBBRRBBBB\nBBBBBRRBBB\nBBBBBBRRBB\nBBBBBBBRRB\nBBBBBBBBRR\nBBBBBBBBBR"},{"iden":"sample output 3","content":"2"},{"iden":"sample input 4","content":"17\nRBBRRBRRRRRBBBBBB\nBBRBRBRRBRRBRRBBR\nBRBRBBBRBBRBBRBBB\nRBRRBBBBBBRRBRRRR\nRRRRRBRBRRRBBRBBR\nRRRRRBRRBRBBRRRBB\nBBBRRRBRBRBBRRRBB\nBBRRRBRBBBRBRRRBR\nRRBBBBBBBBBBBRBRR\nRRRBRRBRBRBRBRBBB\nRRBRRRRBRBRRBRBBR\nRRRBBRBRBBBRBBRBR\nBBRBBRRBRRRBBRBBB\nBBBRBRRRRRRRBBRBB\nRRRRRBRBRBBRRBRRR\nBRRRRBBBRRRBRRBBB\nBBRRBBRRRBBBRBBBR"},{"iden":"sample output 4","content":"8"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}