← 返回题目列表

AtCoder · ttpc2019_o

O. 姐姐谜题

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

配点: 100 点

問題文(一行)

S 减去 G 到的自避行 (self-avoiding walk) 数为 N 的网格地图,请创建并输出。

問題文(詳細)

oneesan 可以高速解决以下问题。

N,H,W 以及满足以下条件的高度 H、幅 W 的网格地图。

  • 高度 H 幅 W 的网格地图中,H 个长度 W 的字符串 S_1, S_2, \ldots, S_H 代表。
  • 每个格子分别表示为墙 # 、空地 . 、始点 S 、終点 G 中的四个字符之一。
  • 外周全部为墙 # 。
  • 始点 S 和终点 G 各自正好存在 1 个格子。

在网格地图上,S 减去 G 通过重复移动到上下左右相邻的非墙格子到达 # 时,包括起点和终点在内经过的格子序列称为路径。 路径 P, Q 不同是指经过的格子序列长度不同,或者P_i \ne Q_i 变为 i 存在不同。 在路径中,自回避行走 (self-avoiding walk) 指的是不经过同一格子两次的路径。 在给定的网格地图上,调查不同的自回避行走有多少种,并且它是 N 请回答是否相等。 如果相等,请在一行中输出 Yes,否则 输出 No 。

oneesan 喜欢利用上述能力数自己走的自避行走,但觉得自己生成网格地图来数步很无聊。 于是,oneesan 决定请你来生成网格地图。 会给出

N ,请生成网格地图,使 oneesan 输出 Yes 。 但是,由于 oneesan 的规格限制,网格地图有一些限制。具体请阅读输出项。 在这个约束下,可以说一定存在解答。另外,只要满足约束条件,输出任何解答都是允许的。

制約

  • N 是 您也可以写 0 \leq N \leq 2{,}019 的整数 选择

入力

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

N

出力

按以下格式输出到标准输出。 在

H W
S_1
\vdots
S_H

另外,需要满足以下约束条件。

  • H, W 是 您也可以写 3 \leq H,W \leq 32 的整数 选择
  • S_1, \ldots, S_H 是 您也可以写 #、.、S、G 用由 组成的字符串表示网格地图
  • \lvert S_i\rvert = W
  • 网格地图最外层的字符全部为 # 是
  • 网格地图中恰好有 1 个字符 S 存在
  • 网格地图中恰好有 1 个字符 G 存在
  • 网格地图的 S 减去 G 之前的自回避步行的路径数正好是 N 条。

入力例 1

2

出力例 1

4 4
####
#S.#
#.G#
####

除此输出外,还有其他正确的输出存在。带有


入力例 2

8

出力例 2

5 9
#########
#S......#
#.#.#.#.#
#......G#
#########

入力例 3

184

出力例 3

6 6
######
#S...#
#....#
#....#
#...G#
######

入力例 4

1936

出力例 4

8 27
###########################
#.........................#
#.S####.#####.####...###..#
#...#.....#...#...#.#...#.#
#...#.....#...####..#.....#
#...#.....#...#.....#...G.#
#...#.....#...#......###..#
###########################