0232. The Queen

Имя входного файла:	queen.in
Имя выходного файла:	queen.out
Ограничение по времени:	3 s
Ограничение по памяти:	64 megabytes

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.

Input file

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 (1 ≤ 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.

Output file

You are to output only the requested number.

Example:

queen.in	queen.out
3 2 Q.. ... ...	9

Источник: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Обсудить       Отправить решение



Версия для печати