問題一覧 > 通常問題

No.2412 YOU Grow Bigger!

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 55
作問者 : 👑 AngrySadEight / テスター : 👑 hamamu hari64 hari64
お気に入りにしたユーザー ProblemId : 9882 / 自分の提出
問題文最終更新日: 2023-08-05 10:52:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 401 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。