#P17765. 碎片整理

碎片整理

题目描述

给定一个 N×MN\times M 的网格。第 rr 行、第 cc 列的格子记为 (r,c)(r,c)。

你需要将每个格子沿一条对角线切开。每个格子的切割方向只能是以下两种之一:

  • /
  • \

部分格子的切割方向已经给定,剩余格子用 . 表示,表示尚未决定。

只有每个格子内的对角线是切痕,网格线本身不是切痕。

切割完成后,碎片按照二维区域之间的连通关系划分:只有当两个区域通过一段长度为正的线段相连时,它们才属于同一个碎片;若两个区域仅在一个点处接触,则不视为连通,不属于同一个碎片。

称一个切割后得到的碎片是美丽碎片,当且仅当可以将这个碎片适当旋转,使得其边界上的所有线段都与坐标轴平行。若碎片内部存在洞或由切痕形成的缝,则这些内部边界也必须在同一次旋转后全部与坐标轴平行。切痕形成的缝的两侧均计入碎片的边界。

网格中的内部边定义如下:

  • 上下相邻两个格子之间的长度为 11 的线段称为横边;
  • 左右相邻两个格子之间的长度为 11 的线段称为竖边;
  • 横边和竖边统称为边。

一个 N×MN\times M 的网格中共有 (N−1)M(N-1)M 条横边和 N(M−1)N(M-1) 条竖边。

现在给定 KK 条互不相同的边。你需要判断是否存在一种完整切割方案,使得这 KK 条边中的每一条都完整地包含在某个美丽碎片中。不要求这些边属于同一个碎片。

这里,一条边属于某个碎片,是指这条边的内部点(等价地,其中点)属于该碎片,而不是指这条边是该碎片边界的一部分。

若存在,输出任意一种方案。

输入格式

第一行包含三个整数 N,M,KN,M,K。

接下来 NN 行,每行包含一个长度为 MM 的字符串,表示初始网格。每个字符为 /、\ 或 .:

  • / 或 \ 表示该格子的切割方向已经固定;
  • . 表示该格子的切割方向未定。

接下来 KK 行,每行包含三个整数 di,ai,bid_i,a_i,b_i,表示一条必须属于美丽碎片的内部边。

  • 若 di=0d_i=0,则该边是一条横边,且其上方的格子为 (ai,bi)(a_i,b_i);
  • 若 di=1d_i=1,则该边是一条竖边,且其左侧的格子为 (ai,bi)(a_i,b_i)。

输出格式

若不存在满足条件的切割方案,输出一行:NO

若存在满足条件的切割方案,第一行输出:YES

接下来输出 NN 行,每行包含 MM 个字符,每个字符为 / 或 \,表示一种完整切割方案。

输出方案必须与输入中已经固定的格子方向一致。

样例

样例输入 1

4 4 2
..//
.\./
.\..
\./\
0 3 3
1 3 1

样例输出 1

YES
\\//
/\\/
\\\/
\\/\

样例解释 1

在该切割方案中,输入指定的两条内部边均完整地包含在美丽碎片中。其中相应碎片可以是带有内部缝或洞的环状碎片;判断其是否美丽时,外边界以及缝或洞两侧形成的内部边界都需要在同一次旋转后与坐标轴平行。

仅在格点处相接的两个区域不会被合并为同一个碎片。

样例输入 2

2 3 2
.\.
...
1 2 1
1 2 2

样例输出 2

NO

数据范围与子任务

对于所有测试数据:

  • 2≤N,M≤2002\le N,M\le 200;
  • 0≤K≤(N−1)M+N(M−1)0\le K\le (N-1)M+N(M-1);
  • 初始网格字符只可能是 /、\、.;
  • 给定的 KK 条边两两不同;
  • 若 di=0d_i=0,则 1≤ai≤N−1, 1≤bi≤M1\le a_i\le N-1,\ 1\le b_i\le M;
  • 若 di=1d_i=1,则 1≤ai≤N, 1≤bi≤M−11\le a_i\le N,\ 1\le b_i\le M-1。

子任务:

子任务 分值 限制
1 10 N,M≤4, K≤6N,M\le 4,\ K\le 6,且初始网格中 . 的数量不超过 88
2 30 N,M≤50N,M\le 50 且 K=1K=1
3 N,M≤50N,M\le 50 且所有格子均为 .
4 20 N,M≤50N,M\le 50
5 10 无额外限制