[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 与预先摆放好的棋子之间的互相攻击;但不用考虑预先摆放好的棋子之间的互相攻击。