? 將 軍

?

【問題描述】

?

劉先生最近在學習國際象棋，使用一個叫”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的個數。

?

【樣例輸入輸出】

?

checkmate.in

?

3 3

..N

...

...

?

checkmate.out

2

?

?

Hint

?

BBN

...

...

?

BBN

...

B..

?

雖然看上去下面的方法比上面的優秀，但是N被第三行的B攻擊了。也就是說，你需要避免的有2種情況： 你擺放的bishop之間的互相攻擊以及你擺放的bishop與預先擺放好的棋子之間的互相攻擊；但不用考慮預先擺放好的棋子之間的互相攻擊。