AT_past18_j 反転ゲーム

There is a grid with $ H $ horizontal rows and $ W $ vertical columns. The cell in the $ i $ -th row from the top and $ j $ -th column from the left is denoted by cell $ (i, j) $ . Initially, cell $ (i, j) $ is white if $ S_{i,j} $ is `.`, and black if it is `#`. You are initially at cell $ (1,1) $ . You can move to an adjacent cell in one of the four directions: up, down, left, and right. You cannot exit the grid. Whenever you make a move, the color of the cell you step into flips (from white to black and vice versa). Your objective is to make all the cells white. Find the minimum number of moves required to do so. One can prove that you can always make all the cells white under the given constraints.

The input is given from Standard Input in the following format: > $ H $ $ W $ $ S_{1,1}\ldots S_{1,W} $ $ \vdots $ $ S_{H,1}\ldots S_{H,W} $

Print the answer.

### Sample Explanation 1 By making four moves $ (1,1)\to(1,2)\to(2,2)\to(3,2)\to(2,2) $ , you can make all the cells white. ### Sample Explanation 2 All the cells are initially white, so no moves are required. ### Constraints - $ 1 \leq H,W \leq 4 $ - $ H\times W\geq 2 $ - $ H $ and $ W $ are integers. - $ S_{i,j} $ is `.` or `#`.