#2733. 「JOISC 2016 Day 2」三明治

内存限制:256 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: styx

题目描述

题目译自 JOISC 2016 Day2 T2 「サンドイッチ

JOI 君去参加了 IOI 联♂谊会,会场有一张桌子,桌上有 R \times C 个三明治被摆放成 R C 列。每个三明治都被沿主对角线或者次对角线分割成两个小三明治。

一个小三明治仅当以下两种情况满足时才不能被吃掉:

  1. 与该小三明治在同一个三明治中的另一个三明治还没被吃掉;
  2. 与该小三明治两条直角边相邻的另外两个小三明治中有一个没有被吃掉。

现在 JOI 君想问你,他吃掉每一个三明治时最少要吃掉多少个小三明治?

输入格式

第一行有两个整数 R C ,表示三明治桌子有 R C 列。
之后的 R 行,每行 C 个字母,其中字母 N 表示沿主对角线切割,Z 表示沿次对角线切割。

输出格式

输出包括 R 行,每行 C 个数字,第 i j 列表示吃完第 i j 列的三明治时最少吃了几个小三明治,如果吃不到,输出 -1

样例

输入样例 1

2 3
NZN
ZZN

输出样例 1

10 8 2
8 6 4

样例解释 1

大概吃的顺序是这样的:
(1,3) \rightarrow (2,3) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,1)
或者:
(1,3) \rightarrow (2,3) \rightarrow (2,2) \rightarrow (2,1) \rightarrow (1,1)

输入样例 2

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

输出样例 2

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 \leq R,C \leq 400

具体子任务限制及得分情况如下表:

Subtask 限制 分数
1 1 \leq R,C \leq 50 35
2 无追加限制 65