{"problem":{"name":"Stronger Takahashi","description":{"content":"There is a town divided into a grid of cells with $H$ rows and $W$ columns. The cell at the $i$\\-th row from the top and $j$\\-th column from the left is a passable space if $S_{i,j}$ is `.` and a bloc","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc213_e"},"statements":[{"statement_type":"Markdown","content":"There is a town divided into a grid of cells with $H$ rows and $W$ columns. The cell at the $i$\\-th row from the top and $j$\\-th column from the left is a passable space if $S_{i,j}$ is `.` and a block if $S_{i,j}$ is `#`.\nTakahashi will go from his house to a fish market. His house is in the cell at the top-left corner, and the fish market is in the cell at the bottom-right corner.\nTakahashi can move one cell up, down, left, or right to a passable cell. He cannot leave the town. He cannot enter a block, either. However, his physical strength allows him to destroy all blocks in a square region with $2\\times 2$ cells of his choice with one punch, making these cells passable.\nFind the minimum number of punches needed for Takahashi to reach the fish market.\n\n## Constraints\n\n*   $2 \\leq H,W \\leq 500$\n*   $H$ and $W$ are integers.\n*   $S_{i,j}$ is `.` or `#`.\n*   $S_{1,1}$ and $S_{H,W}$ are `.`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$\n$S_{1,1} \\ldots S_{1,W}$\n$\\vdots$\n$S_{H,1} \\ldots S_{H,W}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc213_e","tags":[],"sample_group":[["5 5\n..#..\n#.#.#\n##.##\n#.#.#\n..#..","1\n\nHe can reach the fish market by, for example, destroying the blocks in the square region with $2\\times 2$ cells marked `*` below.\n\n..#..\n#.**#\n##**#\n#.#.#\n..#..\n\nIt is not required that all of the $2\\times 2$ cells in the region to punch are blocks."],["5 7\n.......\n######.\n.......\n.######\n.......","0\n\nHe can reach the fish market without destroying blocks, though he has to go a long way around."],["8 8\n.#######\n########\n########\n########\n########\n########\n########\n#######.","5"]],"created_at":"2026-03-03 11:01:13"}}