配点: 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.# #...#.....#...#......###..# ###########################