[JLOI2008] 将军

题目描述

刘先生最近在学习国际象棋,使用一个叫 jloi-08 的游戏软件。在这个游戏里,不但可以和电脑普通地对弈,还可以学习著名的棋局,还有针对初学者的规则指导等丰富功能。但是…大小却要 1.4G T\_T。 言归正传,在这个软件里,为了让玩家更好地理解和运用各个棋子,有很多趣味的游戏,比如以下就是一个: 给出一个棋盘和一些棋子,让你把这些棋子摆放在棋盘上,使得两两不互相攻击。你的得分由你摆放上去的棋子的个数与种类有关。 这个游戏很复杂,刘先生老是玩不到高分。于是电脑便降低了难度,替刘先生摆上了一些棋子,最后只给你任意多个 bishop(教主)。 现在刘先生便要考一考你,在电脑给出的这张棋盘上,最多能放几个 bishop。 国际象棋中一共有 6 种棋子: - king(国王); - queen(皇后); - bishop(教主); - knight(骑士); - rook(车); - pawn(步兵)。 各棋子的攻击范围如下: - queen 可以攻击与它在同一行,同一列,同一条对角线的棋子; - knight 的攻击范围如下图所示: ![](https://cdn.luogu.com.cn/upload/pic/2669.png) - rook 攻击水平和垂直两条线上的所有格子; - pawn 攻击前方两条斜线方向各一格(“前方”指 $x$ 递增的方向,$x$ 行 $y$ 列); - king 攻击周围 8 个方向各 1 格; - bishop 攻击两条对角线上的所有格子。 除 knight 以外,所有棋子的攻击范围均会被别的棋子所阻挡。 可惜的是这个软件也不是顶优秀,给出的棋盘上的棋子可能互相会攻击,不过你不用理会这些,你只要保证你摆放的 bishop 不与它们以及不互相攻击就可以了。

输入输出格式

输入格式


第一行是两个整数 $x,y$($1 \leq x,y \leq 1024$)。 下面的 $x$ 行每行 $y$ 个字符表示棋盘。 其中:`K` – king,`Q` – queen,`B` – bishop,`N` – knight,`R` – rook,`P` – pawn,`.` – blank.

输出格式


仅一行一个数,表示最多能够摆放的 bishop 的个数。

输入输出样例

输入样例 #1

3 3
..N
...
...

输出样例 #1

2

说明

```plain BBN ... ... ``` ```plain BBN ... B.. ``` 虽然看上去下面的方法比上面的优秀,但是 N 被第三行的 B 攻击了。也就是说,你需要避免的有 2 种情况: 你摆放的 bishop 之间的互相攻击以及你摆放的 bishop 与预先摆放好的棋子之间的互相攻击;但不用考虑预先摆放好的棋子之间的互相攻击。