logo AlgoBeat OnlineJudge
登录 注册

#101976. [BZOJ 1976] [BeiJing2010组队]能量魔方 Cube

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

题目描述

小 C 有一个能量魔方,这个魔方可神奇了,只要按照特定方式,放入不同的能量水晶,就可以产生巨大的能量。

能量魔方是一个 的立方体,一共用 个空格可以填充能量水晶。

能量水晶有两种:

  • 一种是正能量水晶(Positive
  • 一种是负能量水晶(Negative

当这个魔方被填满后,就会依据填充的能量水晶间的关系产生巨大能量。对于相邻两(相邻就是拥有同一个面)的两个格子,如果这两个格子填充的是一正一负两种水晶,就会产生一单位的能量。而整个魔方的总能量,就是这些产生的能量的总和。

现在,小 C 已经在魔方中填充了一些水晶,还有一些位置空着。他想知道,如果剩下的空格可以随意填充,那么在最优情况下,这个魔方可以产生多少能量。

输入格式

第一行包含一个数 ,表示魔方的大小。

接下来 行,每行 个字符,每个字符有三种可能:

  • P:表示此方格已经填充了正能量水晶;
  • N:表示此方格已经填充了负能量水晶;
  • ?:表示此方格待填充。

上述 行,第 到第 行描述了立方体第 i 层从前到后,从左到右的状态。且每 行间,都有一空行分隔。

输出格式

仅包含一行一个数,表示魔方最多能产生的能量。

样例

样例输入 #1

2
P?
??

??
N?

样例输出 #1

9

样例说明 1

如下状态时,可产生最多的能量。

PN
NP

NP
NN

数据范围与提示

  • 对于 的数据,
  • 对于 的数据,
  • 对于 的数据,
  • 对于 的数据,