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

    ID: 5799 传统题 5000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-状态扩展图Kahn 算法DAG 动态规划

「JOISC 2016 Day 2」三明治

题目描述

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

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

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

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

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

输入格式

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

输出格式

输出包括 RR 行,每行 CC 个数字,第 ii 行 jj 列表示吃完第 ii 行 jj 列的三明治时最少吃了几个小三明治,如果吃不到,输出 −1-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

数据范围与提示

对于全部的数据,1≤R,C≤4001 \leq R,C \leq 400 。

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

Subtask 限制 分数
11 1≤R,C≤501 \leq R,C \leq 50 3535
22 无追加限制 6565