問題一覧 > 通常問題

No.2641 draw X

レベル : / AI推定難易度 : 1425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 45
作問者 : ponjuice / テスター : noya2
お気に入りにしたユーザー ProblemId : 10667 / 自分の提出
問題文最終更新日: 2024-02-19 00:46:49
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
traP 作問ハッカソンコンテスト 002(day2) (順位表) の他の問題:

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