1929. 将军

【题目描述】

刘先生最近在学习国际象棋，使用一个叫”jloi-08”的游戏软件。在这个游戏里，不但可以和电脑普通地对弈，还可以学习著名的棋局，还有针对初学者的规则指导等丰富功能。但是…大小却要1.4G T_T。

言归正传，在这个软件里，为了让玩家更好地理解和运用各个棋子，有很多趣味的游戏，比如以下就是一个：

给出一个棋盘和一些棋子，让你把这些棋子摆放在棋盘上，使得两两不互相攻击。你的得分由你摆放上去的棋子的个数与种类有关。

这个游戏很复杂，刘先生老是玩不到高分。于是电脑便降低了难度，替刘先生摆上了一些棋子，最后只给你任意多个bishop(教主)。

现在刘先生便要考一考你，在电脑给出的这张棋盘上，最多能放几个bishop。

国际象棋中一共有6种棋子：

king     (国王)

queen   (皇后)

bishop  (教主)

knight  (骑士)

rook    (车)

pawn   (步兵)

queen和knight不用说了；rook攻击水平和垂直两条线上的所有格子；pawn攻击前方两条斜线方向各一格；king攻击周围8个方向各1格；bishop攻击两条对角线上的所有格子。

除knight以外，所有棋子的攻击范围均会被别的棋子所阻挡。(“前方”指x递增的方向，x行y列)

可惜的是这个软件也不是顶优秀，给出的棋盘上的棋子可能互相会攻击，不过你不用理会这些，你只要保证你摆放的bishop不与它们以及不互相攻击就可以了。

【输入格式】

第一行是2个整数x, y　(1<=x,y<=1024)，

下面的x行每行y个字符表示棋盘，

其中：K – king, Q – queen, B – bishop, N – knight, R – rook, P – pawn, “.” – blank.

【输出格式】

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

【样例输入】

3 3

..N

...

...

【样例输出】

2

【提示】

Hint

BBN

...

...

BBN

...

B..

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

【来源】