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

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

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

在上图中,,每条对角线费用均为 。左侧贴纸有 条水平线段、 条竖直线段和 条对角线段,费用为 ;右侧贴纸的费用为 。
请计算每张贴纸能够达到的最小打磨费用。可以证明,存在一种同时裁出所有贴纸的方式,使每一张贴纸都同时达到各自的最小费用。

上图对应样例2,三张贴纸的费用分别为 。注意孔洞边界也计费。
输入格式
第一行包含一个整数 ,表示测试用例数。
对于每个测试用例:
- 第一行包含四个整数 。
- 接下来 行,每行一个长度为 的字符串,只含
/和\,表示各方格中对角线的方向。输入中反斜杠实际写作字符\,不是两个字符。 - 接下来 行,每行一个长度为 的字符串,只含
#和.。对第 行、第 列方格,字符 表示对角线左侧三角形,字符 表示右侧三角形;#表示填色,.表示未填色。这里 均从 开始。 - 接下来 行,每行 个整数,其中第 行为 。
数据范围
- 。
- 、,。
- 。
- 每个测试用例至少产生 张、至多产生 张贴纸。
- 不存在某个填色三角形的一条边同时也是整张纸的边界。
原题没有对所有测试用例的 之和作额外限制。
输出格式
每个测试用例输出两行。
第一行输出贴纸总数 。第二行输出 个整数,为各张贴纸的最小打磨费用,按非递减顺序排列。
样例输入 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