传统题 5000ms 256MiB

三明治

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

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

  1. 与该小三明治在同一个三明治中的另一个三明治还没被吃掉;

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

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

1<=R,C<=400

Input Format

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

Output Format

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

2 3
NZN
ZZN​
10 8 2
8 6 4​
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

Hint

样例1大概吃的顺序是这样的:

(1,3)→(2,3)→(2,2)→(1,2)→(1,1)或者:

(1,3)→(2,3)→(2,2)→(2,1)→(1,1)

寒假第一次训练补题通道

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2021-1-15 17:00
结束于
2021-1-17 21:00
持续时间
52 小时
主持人
参赛人数
0