#P18558. Puzzle: Nurikabe

Puzzle: Nurikabe

Puzzle: Nurikabe

“下一场比赛,我想让你解一道只有两个线索的 Nurikabe。”

“听起来很简单,我来写解法!”

“你确定吗?你做过 Yuhao 的 Fillomino 吗?”

“嗯,等等……”

——小青鱼和某位裁判的对话。

小青鱼喜欢逻辑谜题。今天,他正在玩经典谜题 Nurikabe(ぬりかべ) 的一种特殊版本。

谜题位于一个 n×mn\times m 的棋盘上。第 xx 行、第 yy 列的格子记为 (x,y)(x,y),其中 1≤x≤n1\le x\le n、1≤y≤m1\le y\le m。

你需要将一些格子(也可以一个都不涂)涂黑,其余格子保持白色。同色格子共边时相连,只在角上接触不算相连;同色格子通过这种相邻关系形成连通区域。等价地,同色两格属于同一区域,当它们水平或竖直相邻,或能通过其他同色格子形成一条相邻路径。

原图4:7x7示例棋盘

线索是预先写在特定格子中的数字。带线索的格子必须保持白色。

黑色格子必须同时满足:

  • 所有黑格属于同一个黑色连通区域。
  • 不存在四个格子全部为黑色的 2×22\times2 方块。

白色格子必须同时满足:

  • 每个白色连通区域恰好包含一个线索。
  • 每个白色区域的面积(格子数)等于其中线索的数值。

下面四个原图给出了错误示范,依次为:存在全黑 2×22\times2;黑格不连通;左上白区包含多个线索;左下白区没有线索且右下白区面积不符。

原图5:四种错误方案

下面是对应谜题的一个正确方案。

原图6:正确方案

本题给定的谜题恰好只有一个线索。 请给出满足所有要求的涂色方案。上述原图用于说明一般规则。

输入格式

输入包含多组测试数据。第一行是整数 TT(T≥1T\ge1)。

对于每组数据:

第一行包含两个整数 n,mn,m(n,m≥1n,m\ge1),表示棋盘行数和列数。

第二行包含三个整数 i,j,xi,j,x(1≤i≤n1\le i\le n,1≤j≤m1\le j\le m,1≤x≤n⋅m1\le x\le n\cdot m),表示唯一的线索位于 (i,j)(i,j),数值为 xx。

保证所有测试数据的 n⋅mn\cdot m 之和不超过 10610^6。

输出格式

对于每组数据,若无法满足所有要求,输出一行 No。

否则先输出一行 Yes,接着输出 nn 行,每行恰有 mm 个字符:. 表示白格,# 表示黑格。输出任意合法方案即可。

完整原样例

4
3 3
2 2 1
5 5
2 2 1
4 6
1 1 20
2 5
2 5 10
Yes
###
#.#
###
No
Yes
......
......
#.....
###...
Yes
.....
.....

原题附注

解完所有题之后,想再找点乐趣吗?这里还有一幅谜题。

原图7:第二届Universal Cup谜题赛Nurikabe,出自apiad