Comet OJ

C0647 [BJWC2010]能量魔方

内存限制：256 MB 时间限制：1000 ms

题目描述

小 C 有一个能量魔方，这个魔方可神奇了，只要按照特定方式，放入不同的 能量水晶，就可以产生巨大的能量。 能量魔方是一个 $N*N*N$ 的立方体，一共用 $N^3$ 个空格可以填充能量水晶。 能量水晶有两种：

一种是正能量水晶(Positive)

一种是负能量水晶(Negative)

当这个魔方被填满后，就会依据填充的能量水晶间的关系产生巨大能量。对于相邻（相邻就是拥有同一个面）的两个格子，如果这两个格子填充的是一正一 负两种水晶，就会产生一单位的能量。而整个魔方的总能量，就是这些产生的能量的总和。 现在，小 C 已经在魔方中填充了一些水晶，还有一些位置空着。他想知道，如果剩下的空格可以随意填充，那么在最优情况下，这个魔方可以产生多少能量。

输入格式

第一行包含一个数 $N$，表示魔方的大小。

接下来 $N^2$ 行，每行 $N$ 个字符，每个字符有三种可能：

P：表示此方格已经填充了正能量水晶；

N：表示此方格已经填充了负能量水晶；

?：表示此方格待填充。

上述 $N*N$ 行，第 $(i-1)*N+1$ ~ $i*N$ 行描述了立方体第 $i$ 层从前到后，从左到右的状态。且每 $N$ 行间，都有一空行分隔。

输出

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

样例

样例输入 1

2
P?
??

??
N?

样例输出 1

9

提示

【样例说明】

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

PN
NP

NP
NN

【数据规模】

10% 的数据 $N≤3$；

30% 的数据 $N≤4$；

80% 的数据 $N≤10$；

100% 的数据 $N≤40$。