{"problem":{"name":"Routing","description":{"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 init","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc177_c"},"statements":[{"statement_type":"Markdown","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?\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc177_c","tags":[],"sample_group":[["5\nRBRBB\nRBRRR\nRRRBR\nRBBRB\nBBRBR","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)"],["5\nRBBBB\nBBBBB\nBBBBB\nBBBBB\nBBBBR","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)"],["10\nRRBBBBBBBB\nBRRBBBBBBB\nBBRRBBBBBB\nBBBRRBBBBB\nBBBBRRBBBB\nBBBBBRRBBB\nBBBBBBRRBB\nBBBBBBBRRB\nBBBBBBBBRR\nBBBBBBBBBR","2"],["17\nRBBRRBRRRRRBBBBBB\nBBRBRBRRBRRBRRBBR\nBRBRBBBRBBRBBRBBB\nRBRRBBBBBBRRBRRRR\nRRRRRBRBRRRBBRBBR\nRRRRRBRRBRBBRRRBB\nBBBRRRBRBRBBRRRBB\nBBRRRBRBBBRBRRRBR\nRRBBBBBBBBBBBRBRR\nRRRBRRBRBRBRBRBBB\nRRBRRRRBRBRRBRBBR\nRRRBBRBRBBBRBBRBR\nBBRBBRRBRRRBBRBBB\nBBBRBRRRRRRRBBRBB\nRRRRRBRBRBBRRBRRR\nBRRRRBBBRRRBRRBBB\nBBRRBBRRRBBBRBBBR","8"]],"created_at":"2026-03-03 11:01:14"}}