No.2641 draw X
Problem Statement
There is a grid-shaped picture $S$ with $H$ rows and $W$ columns. Let $(i,j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.
Cell $(i,j)$ is painted black if $S_{i,j}=$#, and is not painted if $S_{i,j}=$..
You want to draw the same picture on a blank grid-shaped canvas $T$ with $H$ rows and $W$ columns by drawing X-shaped figures any number of times. That is, you want the following conditions to hold for all $i,j$.
- If $S_{i,j}=$
#, cell $(i,j)$ of $T$ is painted black. - If $S_{i,j}=$
., cell $(i,j)$ of $T$ is not painted.
Determine whether you can draw this picture.
Drawing an X shape means the following.
- Choose a center cell $(x,y)$ and an integer $r$ as its size. $(\ 2 \leq x \leq H-1,\ 2 \leq y \leq W-1, 1 \leq r \leq \min(x-1,y-1,H-x,W-y))$
- For every integer $k$ satisfying $-r \leq k \leq r$, paint $(x+k, y+k)$ black.
- For every integer $k$ satisfying $-r \leq k \leq r$, paint $(x+k, y-k)$ black.
Constraints
- $H,W$ are integers
- $1 \leq H, W$
- $1 \leq H \times W \leq 10^6$
- $S_{i,j}$ is
#or.
Input
$H\ W$
$S_{1,1}S_{1,2}\cdots S_{1,W}$
$\vdots$
$S_{H,1}S_{H,2}\cdots S_{H,W}$
Output
Print Yes if you can draw the picture, and No otherwise.
Sample
Sample 1
Input
5 5 #...# .#.#. ..#.# .#.#. #.#.#
Output
Yes
You can draw this picture by drawing an X of size $2$ at $(3,3)$ and an X of size $1$ at $(4,4)$.
Sample 2
Input
3 3 #.# .#. ###
Output
No
No matter how you draw X shapes, cell $(3,2)$ cannot be painted.
Sample 3
Input
10 12 ###.......#. .#.#.....#.. ..#.#...#... ...#.#.#.... ....#.#..... .....#.#.... ....#.#.#... ...#...#.#.. ..#.....#.#. .#.......###
Output
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2