No.2412 YOU Grow Bigger!
タグ : / 解いたユーザー数 55
作問者 : 👑
hamamu
hari64
Problem Statement
There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by cell $(i, j)$. Some cells contain spikes.
The state of the grid is given by strings $S_1, S_2, \dots, S_H$. If $S_{i, j}$ is #, cell $(i, j)$ contains a spike; if it is ., it does not.
Alice is on the grid. However, due to a mysterious power, her body has been made $3$ times larger. Specifically, Alice occupies a region of $3 \times 3$ cells that are contiguous vertically and horizontally (see the figure below).
The region where Alice is located is written in the form $(x_1, y_1, x_2, y_2)$, using the top-left cell $(x_1, y_1)$ and the bottom-right cell $(x_2, y_2)$ of the region she occupies.
Alice can move in any of the $8$ directions (up, down, left, right, and diagonally), only if the region occupied by her body stays within the grid. Strictly speaking, the following moves are possible.
- Change the region where Alice is located from $(i, j, i + 2, j + 2)$ to $(i + 1, j, i + 3, j + 2)$.
- Change the region where Alice is located from $(i, j, i + 2, j + 2)$ to $(i + 1, j + 1, i + 3, j + 3)$.
- Change the region where Alice is located from $(i, j, i + 2, j + 2)$ to $(i, j + 1, i + 2, j + 3)$.
- Change the region where Alice is located from $(i, j, i + 2, j + 2)$ to $(i - 1, j + 1, i + 1, j + 3)$.
- Change the region where Alice is located from $(i, j, i + 2, j + 2)$ to $(i - 1, j, i + 1, j + 2)$.
- Change the region where Alice is located from $(i, j, i + 2, j + 2)$ to $(i - 1, j - 1, i + 1, j + 1)$.
- Change the region where Alice is located from $(i, j, i + 2, j + 2)$ to $(i, j - 1, i + 2, j + 1)$.
- Change the region where Alice is located from $(i, j, i + 2, j + 2)$ to $(i + 1, j - 1, i + 3, j + 1)$.
However, if at least one of the cells Alice would occupy at the destination contains a spike, that move cannot be made.
Alice wants to move from region $(1, 1, 3, 3)$ to region $(H - 2, W - 2, H, W)$.
Meanwhile, Bob wants to place spikes on some cells so that Alice cannot move in this way. However, spikes cannot be placed on cells inside region $(1, 1, 3, 3)$ or region $(H - 2, W - 2, H, W)$.
Find the minimum number of cells on which spikes must be placed so that Alice cannot move from region $(1, 1, 3, 3)$ to region $(H - 2, W - 2, H, W)$.
Constraints
- $H, W$ are integers.
- $H, W \geq 6$
- $H \times W \leq 2400$
- $S_i$ is a string of length $W$ consisting of
.and#. - $S_{i, j} =$
.(when $1 \leq i \leq 3$ and $1 \leq j \leq 3$) - $S_{i, j} =$
.(when $H - 2 \leq i \leq H$ and $W - 2 \leq j \leq W$)
Input
The input is given from Standard Input in the following format.
$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$
Output
Output the answer.
Sample
Sample 1
Input
7 7 ....... ....... ....... .#...#. ....... ....... .......
Output
1
If a spike is placed on cell $(4, 4)$, Alice can no longer reach region $(5, 5, 7, 7)$.
Sample 2
Input
7 7 ......# .....#. ....#.. ...#... ..#.... .#..... #......
Output
0
Even without placing any spikes, Alice cannot reach region $(5, 5, 7, 7)$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。