? 將 軍

?

【問題描述】

?

劉先生最近在學(xué)習(xí)國(guó)際象棋，使用一個(gè)叫”jloi-08”的游戲軟件。在這個(gè)游戲里，不但可以和電腦普通地對(duì)弈，還可以學(xué)習(xí)著名的棋局，還有針對(duì)初學(xué)者的規(guī)則指導(dǎo)等豐富功能。但是…大小卻要1.4G T_T。

?

言歸正傳，在這個(gè)軟件里，為了讓玩家更好地理解和運(yùn)用各個(gè)棋子，有很多趣味的游戲，比如以下就是一個(gè)：

給出一個(gè)棋盤和一些棋子，讓你把這些棋子擺放在棋盤上，使得兩兩不互相攻擊。你的得分由你擺放上去的棋子的個(gè)數(shù)與種類有關(guān)。

?

這個(gè)游戲很復(fù)雜，劉先生老是玩不到高分。于是電腦便降低了難度，替劉先生擺上了一些棋子，最后只給你任意多個(gè)bishop(教主)。

?

現(xiàn)在劉先生便要考一考你，在電腦給出的這張棋盤上，最多能放幾個(gè)bishop。

?

國(guó)際象棋中一共有6種棋子：

king???? ( 國(guó)王)

queen?? ( 皇后)

bishop? ( 教主)

knight? ( 騎士)

rook??? ( 車)

pawn?? ( 步兵)

?

queen 和knight不用說(shuō)了；rook攻擊水平和垂直兩條線上的所有格子；pawn攻擊前方兩條斜線方向各一格；king攻擊周圍8個(gè)方向各1格；bishop攻擊兩條對(duì)角線上的所有格子。

?

除knight以外，所有棋子的攻擊范圍均會(huì)被別的棋子所阻擋。(“前方”指x遞增的方向，x行y列)

?

可惜的是這個(gè)軟件也不是頂優(yōu)秀，給出的棋盤上的棋子可能互相會(huì)攻擊，不過(guò)你不用理會(huì)這些，你只要保證你擺放的bishop不與它們以及不互相攻擊就可以了。

?

【輸入】

?

第一行是2個(gè)整數(shù)x, y　(1<=x,y<=1024)，

下面的x行每行y個(gè)字符表示棋盤，

?

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

?

【輸出】

?

僅一行一個(gè)數(shù)，表示最多能夠擺放的bishop的個(gè)數(shù)。

?

【樣例輸入輸出】

?

checkmate.in

?

3 3

..N

...

...

?

checkmate.out

2

?

?

Hint

?

BBN

...

...

?

BBN

...

B..

?

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