P14398 [JOISC 2016] 三明治 / Sandwich

JOI 君正在参加 JOI 公司的联谊会。联谊会上，三明治被摆放在一个 $R$ 行 $C$ 列的正方形网格中。每个三明治的形状为等腰直角三角形，其两条直角边的长度等于网格边长，且每个网格内放置两个三明治，它们的斜边彼此相邻。下图展示了三明治的摆放示例。 :::align{center}  ::: 同时满足以下两个条件的三明治不可被取走： - 其斜边与另一个尚未被取走的三明治相邻。 - 除斜边外的两条边中，至少有一条边与另一个尚未被取走的三明治相邻。 除此之外的三明治均可取走。 初始状态下，所有三明治均未被取走。从初始状态开始，若要取走某个三明治，可能需要先取走其他若干个三明治。根据三明治的摆放方式，也可能存在某些三明治从一开始便不可取。 JOI 君希望吃掉放在同一网格中的两个三明治，但他尚未决定具体选择哪个网格。 从初始状态开始，当他打算取走某个网格中的两个三明治时，他关心的是：必须取走的三明治的最少数量。 **问题** 给定三明治的摆放方式，对于每个网格，请判断：通过取走若干个三明治，是否可以取走该网格中的两个三明治；若可以，求出必须取走的三明治的最少数量（该数量包括目标的两个三明治）。

从标准输入读取以下数据： - 第 1 行包含两个整数 $R$、$C$，以空格分隔。这表示三明治被摆放在一个 $R$ 行 $C$ 列的正方形网格中。 - 接下来的 $R$ 行中，第 $i$ 行（$1 \le i \le R$）包含一个长度为 $C$ 的字符串。每个字符为 'N' 或 'Z'。该字符串从左至右的第 $j$ 个字符（$1 \le j \le C$）表示第 $i$ 行第 $j$ 列网格中三明治的摆放方式。'N' 和 'Z' 分别表示以下两种摆放方式。 :::align{center}  :::

请向标准输出输出 $R$ 行。第 $i$ 行（$1 \le i \le R$）应输出 $C$ 个整数，以空格分隔。第 $j$ 个整数（$1 \le j \le C$）表示：当尝试取走第 $i$ 行第 $j$ 列网格中的两个三明治时，必须取走的三明治的最少数量。若无法取走，则输出 $-1$。

### 样例 1 解释 输入样例 1 中的三明治摆放方式对应题目文本中的图 1。 例如，要取走第 2 行第 2 列网格中的两个三明治，可以按以下顺序取走三明治： - 取走第 1 行第 3 列网格右上方的三明治。 - 取走第 1 行第 3 列网格左下方的三明治。 - 取走第 2 行第 3 列网格右上方的三明治。 - 取走第 2 行第 3 列网格左下方的三明治。 - 取走第 2 行第 2 列网格右下方的三明治。 - 取走第 2 行第 2 列网格左上方的三明治。 总共需取走 6 个三明治，由于这是最小值，因此输出 6。 ### 数据范围 所有输入数据均满足以下条件： - $1 \le R \le 400$。 - $1 \le C \le 400$。 ### 子任务 **子任务 1 [35 分]** 满足以下条件： - $R \le 50$。 - $C \le 50$。 **子任务 2 [65 分]** 无额外限制。 翻译由 Qwen3-235B 完成