#P18616. Printing Stickers

Printing Stickers

Printing Stickers

ICPC 公司有一台贴纸打印机。它使用一张由 MM 行、NN 列单位方格组成的纸。每个方格沿给定的一条对角线分成两个三角形,其中一些三角形被填上了墨水。

原题图8:裁剪前的纸张

打印后要将纸裁成若干张贴纸。只能沿三角形的边切割,并且任何填色三角形的任何一条边都不能作为切割线。裁剪后,没有填色三角形的纸片会被丢弃。每张保留的贴纸至少有一个填色三角形,并且其中的全部填色三角形必须连通:任意两个填色三角形之间,都能通过一串填色三角形连接,其中相邻两个至少有一个公共点。

原题图9:只有最左侧的裁剪合法

每张贴纸都需要打磨边界。如果贴纸内有孔洞,孔洞的边界也要打磨。边界上的每条单位水平网格边的打磨费用为 HH,每条单位竖直网格边的费用为 VV。第 ii 行、第 jj 列方格的对角线若成为边界,打磨费用为 DijD_{ij}。贴纸的总费用为其全部边界线段费用之和。

原题图10:打磨费用示意

在上图中,H=V=10H=V=10,每条对角线费用均为 11。左侧贴纸有 44 条水平线段、44 条竖直线段和 66 条对角线段,费用为 8686;右侧贴纸的费用为 106106。

请计算每张贴纸能够达到的最小打磨费用。可以证明,存在一种同时裁出所有贴纸的方式,使每一张贴纸都同时达到各自的最小费用。

原题图11:样例2与孔洞边界

上图对应样例2,三张贴纸的费用分别为 723,196,214723,196,214。注意孔洞边界也计费。

输入格式

第一行包含一个整数 TT,表示测试用例数。

对于每个测试用例:

  1. 第一行包含四个整数 M,N,H,VM,N,H,V。
  2. 接下来 MM 行,每行一个长度为 NN 的字符串,只含 / 和 \,表示各方格中对角线的方向。输入中反斜杠实际写作字符 \,不是两个字符。
  3. 接下来 MM 行,每行一个长度为 2N2N 的字符串,只含 # 和 .。对第 ii 行、第 jj 列方格,字符 2j−12j-1 表示对角线左侧三角形,字符 2j2j 表示右侧三角形;# 表示填色,. 表示未填色。这里 i,ji,j 均从 11 开始。
  4. 接下来 MM 行,每行 NN 个整数,其中第 ii 行为 Di1,Di2,…,DiND_{i1},D_{i2},\ldots,D_{iN}。

数据范围

  • 1≤T≤501\le T\le50。
  • M≥2M\ge2、N≥2N\ge2,4≤M×N≤100004\le M\times N\le10000。
  • 1≤H,V,Dij≤10001\le H,V,D_{ij}\le1000。
  • 每个测试用例至少产生 11 张、至多产生 10001000 张贴纸。
  • 不存在某个填色三角形的一条边同时也是整张纸的边界。

原题没有对所有测试用例的 M×NM\times N 之和作额外限制。

输出格式

每个测试用例输出两行。

第一行输出贴纸总数 kk。第二行输出 kk 个整数,为各张贴纸的最小打磨费用,按非递减顺序排列。

样例输入 1

1
4 9 10 10
\////\\/\
\\/\//\//
//\\/\\/\
\///\//\/
.....#...##.......
.##.#.....##...##.
...#.##....####...
..#.........#..##.
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1

样例输出 1

2
86 106

样例输入 2

1
8 12 20 19
\//\//\/\\\/
//\/\\\/////
///\/\\\\//\
\//\\\/\/\/\
\\\\\///\///
///\\\\\\\\\
//\/////\\\\
/////\//////
........................
..##################....
..##..............##....
..##..######....##......
..##..##......####..##..
..##........##......##..
..############....####..
........................
11 12 13 15 14 12 17 16 14 13 11 10
12 13 15 14 13 17 18 17 15 14 12 16
16 17 18 17 15 14 13 11 16 17 18 19
19 11 12 13 15 14 16 16 17 18 14 13
13 20 16 15 14 14 13 11 10 12 12 13
16 17 17 14 15 16 19 12 14 11 14 16
18 17 14 14 16 19 18 14 15 13 12 14
15 16 17 15 11 18 19 16 16 14 14 20

样例输出 2

3
196 214 723