No tags yet

No tag edit access

time limit per test: 0.5 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard

output: standard

output: standard

You are given a chessboard with side equal to N. There are some chess pieces on it. The only White Queen on the board is able to move and to attack black pieces. Other pieces are not allowed to move or to attack any pieces. You are given a position of all chess pieces on the board. Your task is to find, how many different cells on the field the White Queen can occupy after exactly M moves.

The first line of input contains an integer number N: side of the chessboard (2<=N<=300). The second line contains an integer number M: number of moves the Queen has to do (0<=M<=50). N lines follow first two lines, with N symbols in each. They show the positions of the figures on the chessboard. Each symbol may be 'W', it tells you that a white piece (not a queen) occupies this cell, 'B' tells you that a black piece does so. 'Q' is the White Queen. There can be unlimited number of pieces of each type on the board, but it's guaranteed that there will be exactly one White Queen. A dot '.' tells you, that there are no pieces in this cell of chessboard. All Latin letters in the input are uppercase.

You are to output only the requested number.

Input

3

2

Q..

...

...

2

Q..

...

...

Output

9

Author: | Antony Popovich |

Resource: | --- |

Date: | November, 2003 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2019 04:26:19 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|