問題一覧 > 通常問題

No.2641 draw X

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : ponjuice / テスター : noya2
4 ProblemId : 10667 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-19 00:46:49

問題文

縦 HH マス、横 WW マスのグリッド状の絵 SS があり、上から ii 行目・左から jj 列目のマスを (i,j)(i,j) とします。 マス (i,j)(i,j) は Si,j=S_{i,j}=#のとき黒色に塗られていて、 Si,j=S_{i,j}=.のとき色は塗られていません。

あなたは、縦 HH マス、横 WW マスのグリッド状の何も塗られていないキャンバス TT に、Xの形をした図形を好きな回数描くことで同じ絵を描きたいです。つまり、全ての i,ji,j に対して次の条件が成り立つようにしたいです。

  • Si,j=S_{i,j}= # のとき TT のマス (i,j)(i,j) は黒く塗られている。
  • Si,j=S_{i,j}= . のとき TT のマス (i,j)(i,j) は何も塗られていない。

あなたはこの絵を描くことができるか判定してください。

Xの形を描くとは以下のことを言います。

  • 中心となるマス (x,y)(x,y) とその大きさとなる整数 rr を決める。( 2≤x≤H−1, 2≤y≤W−1,1≤r≤min⁡(x−1,y−1,H−x,W−y))(\ 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))
  • −r≤k≤r-r \leq k \leq r を満たす全ての整数kkについて、(x+k,y+k)(x+k, y+k) を黒く塗る。
  • −r≤k≤r-r \leq k \leq r を満たす全ての整数kkについて、(x+k,y−k)(x+k, y-k) を黒く塗る。

制約

  • H,WH,W は整数
  • 1≤H,W1 \leq H, W
  • 1≤H×W≤1061 \leq H \times W \leq 10^6
  • Si,jS_{i,j} は#または.

入力

H WH\ W
S1,1S1,2⋯S1,WS_{1,1}S_{1,2}\cdots S_{1,W}
⋮\vdots
SH,1SH,2⋯SH,WS_{H,1}S_{H,2}\cdots S_{H,W}

出力

もし描くことができるのならば Yes を、そうでなければ No を出力してください

サンプル

サンプル1
入力
5 5
#...#
.#.#.
..#.#
.#.#.
#.#.#
出力
Yes

(3,3)(3,3) に大きさ 22 の X を描き、(4,4)(4,4) に大きさ 11 の X を描くと、この絵を描くことができます

サンプル2
入力
3 3
#.#
.#.
###
出力
No

どのようにXを描いたとしても (3,2)(3,2) のマスを塗ることができません

サンプル3
入力
10 12
###.......#.
.#.#.....#..
..#.#...#...
...#.#.#....
....#.#.....
.....#.#....
....#.#.#...
...#...#.#..
..#.....#.#.
.#.......###
出力
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。