题目描述

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$。

2 3
NZN
ZZN

10 8 2
8 6 4

2 2
NZ
ZN

-1 -1
-1 -1

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

10 12 14 16 2
8 -1 -1 -1 4
6 -1 -1 -1 6
4 -1 -1 -1 8
2 16 14 12 10

提示

样例 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 完成