← 返回题目列表

AtCoder · utpc2025_h

H. Heyawake 类问题

中文机器翻译题面 查看原题

配点 : 100 点

問題文

(3N+1) 行 (3N+1) 列的格子。判断是否有可能以“黑”或“白”填充每个格子,使其满足以下所有条件,如果可能的话,填充方式为 1 请注明之一。

  • 不同的黑格是辺不共享接触。
  • 以任意的黑格子为起点,角移动到与之共享接触的黑格子, 0 重复至少次数以上,就能够到达与网格外周接触的某个黑格子。
  • 白格子整体是连通的。也就是说,对于任意的 2 个白格子,辺可以移动到与之共享接触的白格子。 0 通过重复以上操作,可以从一方到达另一方。
  • 是 小于或等于 2 行中恰好有 N+1 个黑格子。其他行中恰好有 N 个黑格子。
  • 是 小于或等于 2 列中恰好有 N+1 个黑格子。其他列中恰好有 N 个黑格子。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 500

入力

输入是按以下格式从标准输入给出的。

N

出力

如果不存在满足条件的涂色方式,1 行 No 则输出。 否则,将满足条件的涂色方式按以下格式输出。从上到下 i 行,从左数 j 列的格子是白色,则为 a_{i,j} 该值应乘以 . ,如果是黑色,则为 # 。

Yes
a_{1,1} \dots a_{1,3N+1}
\vdots
a_{3N+1,1} \dots a_{3N+1,3N+1}

。 如果存在多个满足条件的涂色方式,无论输出哪一个都是正确答案。


入力例 1

1

出力例 1

No

下面 3 个输出例子 N=1 符合输出格式,但由于不满足条件,将被判定为错误。

Yes
##..
#...
...#
..##
Yes
#.#.
...#
#.#.
.#..
Yes
...#
.#..
..#.
#...

1 在第一个例子中,黑格子是通过边相连的。\n

2 在第二个例子中,白格子整体上不是连通的。\n

3 在第三个例子中,不仅不满足黑格子的数量条件,而且例如从上方第\n 2 行,从左数 2 列的黑格子作为起点,反复移动到共角相连的黑格子,也无法到达与格子外周接触的黑格子。\n

N=1 在这种情况下,可以证明不存在满足条件的涂色方法。\n