P12744 [POI 2016 R3] 树篱 Hedge

翻译来自于 [LibreOJ](https://loj.ac/p/5040)。

**题目译自 [XXIII Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi23-3/dashboard/) [Żywopłot](https://szkopul.edu.pl/problemset/problem/dABzva_j1-BvzKMsyxkuRoue/statement/)** 王室园丁 Bajtazar 受命在王宫花园中打造一座树篱迷宫。花园可划分为 $m \times n$ 个方格，周围环绕着一圈围墙，北墙和南墙的正中各有一入口。在每条分隔两个方格的边上，可以种植一段树篱——使用杜松或侧柏。国王更偏爱杜松，希望迷宫中尽可能多地使用杜松树篱。然而，杜松对土壤要求较高，无法在所有边上种植。 要让树篱构成迷宫，必须满足一个额外条件：从任一入口出发，都能到达每个方格，且路径唯一（从一个方格可直接进入相邻方格，前提是分隔两者的边上没有树篱。两条路径若经过的方格集合不同，则视为不同路径）。  如上图所示，左侧展示了一个 $m=4, n=5$ 的示例花园，包含 $31$ 条边，其中 $13$ 条边可种植杜松树篱。 右侧展示了一个示例迷宫，包含 $12$ 段树篱，其中 $10$ 段为杜松，$2$ 段为侧柏。这是杜松树篱数量最多的迷宫。你的任务是编写程序，帮助 Bajtazar 设计这样的迷宫。

第一行包含两个整数 $m, n$ $(2 \leq m, n, n$ 为奇数$)$，表示花园的尺寸。 接下来的 $m$ 行，每行包含 $n-1$ 个字符，描述垂直边（按行从左到右读取）。字符 `C` 表示该边可种植杜松树篱，`T` 表示可种植侧柏树篱。 接下来的 $m-1$ 行，每行包含 $n$ 个字符，描述水平边（同样按行从左到右读取）。

第一行输出两个整数，分别表示构成迷宫的树篱段数和其中杜松树篱的最大数量。 接下来的 $2m-1$ 行描述迷宫的边（按输入顺序）。若某边有树篱，输出 `Z`；否则输出 `.`。 若存在多个满足国王要求的解，输出任意一个即可。

**样例 1 解释** 输入数据描述了图左侧的花园；输出结果描述了图右侧的迷宫。 若程序仅正确输出第一行，而后续输出不正确，可获得该测试点 $52\%$ 的分数。特别地，仅输出第一行也可获得 $52\%$ 的分数。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \cdot m \leq 12$ | $25$ | | $2$ | $n, m \leq 100$ | $25$ | | $3$ | $n, m \leq 1000$ | $50$ |