{"problem":{"name":"Ex - Unite","description":{"content":"We have a grid with $N$ rows and $M$ columns, where each square is painted black or white. Here, at least one square is painted black.   The initial state of the grid is given as $N$ strings $S_1,S_2,","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc296_h"},"statements":[{"statement_type":"Markdown","content":"We have a grid with $N$ rows and $M$ columns, where each square is painted black or white. Here, at least one square is painted black.  \nThe initial state of the grid is given as $N$ strings $S_1,S_2,\\ldots,S_N$ of length $M$.  \nThe square at the $i$\\-th row from the top and $j$\\-th column from the left is painted black if the $j$\\-th character of $S_i$ is `#`, and white if it is `.`.\nTakahashi wants to repaint some white squares (possibly zero) black so that the squares painted black are **connected**. Find the minimum number of squares he needs to **repaint** to achieve his objective.\nHere, the squares painted black are said to be **connected** when, for every pair of squares $(S,T)$ painted black, there are a positive integer $K$ and a sequence of $K$ squares $X=(x_1,x_2,\\ldots,x_K)$ painted black such that $x_1=S$, $x_K=T$, and $x_i$ and $x_{i+1}$ share a side for every $1\\leq i\\leq K-1$.  \nIt can be proved that, under the constraints of the problem, there is always a way for Takahashi to achieve his objective.\n\n## Constraints\n\n*   $1 \\leq N \\leq 100$\n*   $1\\leq M \\leq 7$\n*   $N$ and $M$ are integers.\n*   $S_i$ is a string of length $M$ consisting of `#` and `.`.\n*   The given grid has at least one square painted black.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc296_h","tags":[],"sample_group":[["3 5\n...#.\n.#...\n....#","3\n\nThe initial grid looks as follows, where $(i,j)$ denotes the square at the $i$\\-th row from the top and $j$\\-th column from the left.\n![image](https://img.atcoder.jp/abc296/d5b5d945798a02840b8add26271fe2a5.png)\nAssume that Takahashi repaints three squares $(2,3),(2,4),(3,4)$ (shown red in the figure below) black.\n![image](https://img.atcoder.jp/abc296/d2d0f1745af0dc309341f96dbd83e717.png)\nThen, we have the following squares painted black, including the ones painted black from the beginning. These squares are connected.\n![image](https://img.atcoder.jp/abc296/76bebc05c2d7c5240151b534ba30f29b.png)\nIt is impossible to repaint two or fewer squares black so that the squares painted black are connected, so the answer is $3$.  \nNote that the squares painted white do not have to be connected."],["3 3\n###\n###\n###","0\n\nAll squares might be painted black from the beginning."],["10 1\n.\n#\n.\n.\n.\n.\n.\n.\n#\n.","6"]],"created_at":"2026-03-03 11:01:14"}}