<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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
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.

Output
You are to output only the requested number.

Sample test(s)

Input
3
2
Q..
...
...

Output
9
Author:	Antony Popovich
Resource:	---
Date:	November, 2003

<|response|>
## 1) Abridged problem statement (concise)

Given an \(N \times N\) chessboard (\(2 \le N \le 300\)) containing:

- `Q` = the only white queen (the only piece that can move),
- `W` = other white pieces (immovable blockers),
- `B` = black pieces (can be captured),
- `.` = empty,

the queen moves like a normal chess queen (any number of squares in 8 directions), **cannot pass through any piece**, **cannot land on `W`**, but **may land on `B`** (capture) and then must stop in that direction.

Count how many distinct cells the queen can occupy **after exactly \(M\) moves** (\(0 \le M \le 50\)).

---

## 2) Key observations

1. **Moves form a directed graph on cells**  
   From a cell \((x,y)\), edges go to all cells visible along the 8 queen directions until blocked:
   - stop before `W` (cannot enter),
   - can enter `B` but stop there (cannot pass),
   - can traverse `.` freely.

2. **We need “exactly \(M\) moves”, not “at most \(M\)”**  
   A standard technique: track minimal moves to reach each cell, but also whether we can “waste” moves.

3. **Parity (even/odd) is what matters beyond the minimum**  
   If you can reach a cell in \(d\) moves and you can insert a 2-move detour somewhere (a “bounce”), then you can also reach it in \(d+2, d+4, \dots\).  
   So for each cell we only need:
   - minimal even distance,
   - minimal odd distance.

4. **How to model wasting 2 moves (“bounce”)**  
   While scanning a ray (a direction) from a position, besides the normal transition \(d \to d+1\) (one queen move), sometimes we can also set reachability with \(d \to d+2\) (same parity as \(d\)) if a 2-move detour exists (move out and come back / bounce).  
   The reference solution encodes this with a `can_bounce` flag:
   - initially depends on whether the square behind the start (opposite direction) exists and is not `W`,
   - after moving at least one step along the ray, `can_bounce` becomes true.

5. **Small \(M\) allows BFS-by-distance with buckets**  
   Because \(M \le 50\), we can process states in layers `0..M` using buckets (vectors/lists).  
   Relaxations only go to `d+1` and `d+2`.

---

## 3) Full solution approach

### State definition
Let:

\[
dist[x][y][p] = \text{minimum number of moves to reach cell } (x,y) \text{ with parity } p
\]
where \(p \in \{0,1\}\) (0 = even, 1 = odd). Unreachable = -1.

We start at the queen’s initial position with `dist[sx][sy][0] = 0`.

### BFS with buckets (distances up to M)
Maintain `bucket[d]` = list of positions whose minimal distance (with parity `d%2`) is exactly `d`.

For each distance `d` from `0` to `M-1`:
- pop each cell `(x,y)` in `bucket[d]` (ignore stale entries),
- for each of 8 directions, scan outward cell by cell:
  - stop at `W`,
  - allow landing on `.` or `B`,
  - stop after landing on `B`.

During scanning:
- **normal move:** relax `dist[xx][yy][(d+1)%2]` to `d+1`
- **2-move waste (same parity):** if `d+2 <= M` and `can_bounce` is true, relax `dist[xx][yy][d%2]` to `d+2`

The pruning in the reference code stops attempting further relaxations along a ray once it’s provably useless (already dominated by earlier distances with the same parity).

### Extracting the answer
A cell is reachable in **exactly \(M\) moves** if:
- it is reachable with parity \(M \bmod 2\),
- and its minimal distance with that parity is \(\le M\).

The algorithm’s relaxations are designed so that such reachability is captured by `dist[x][y][M%2] != -1` (within processed range).

### Special case: no legal move
If \(M > 0\) and the queen cannot move anywhere at all, then “exactly \(M\) moves” is impossible; answer is 0.
The reference solution checks whether *any* cell besides the start is reachable in any parity; if not, prints 0.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

constexpr pair<int, int> DIRS[] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
                                   {0, 1},   {1, -1}, {1, 0},  {1, 1}};
constexpr int INF = 1e9;

int n, m;
vector<string> tbl;

void read() {
    cin >> n >> m;
    tbl.resize(n);
    cin >> tbl;
}

void solve() {
    // We can't pass over white pieces, and can capture (land on but not pass
    // through) black pieces. We want the count of cells reachable in exactly M
    // moves. BFS over (x, y, distance). Since a cell at distance d is also
    // reachable at d+2 (waste 2 moves bouncing), only parity matters. We store
    // min distance per parity per cell. A cell along a ray can also be reached
    // at distance d+2 if the queen can "bounce" off the wall behind her.
    // Answer: count cells where dist[x][y][m%2] <= m. The complexity of this is
    // O(N^3). The constant might be high, so we might want to terminate faster
    // in the transition loop, and be smart about how we maintain the levels of
    // the BFS (as we have edges of weight 1 and 2). An alternative approach
    // that isn't needed but possible is to have segment tree like structures
    // (compressed edges) over the rows, columns, and diagonals. Then because
    // the transitions are always ranges over one of these three, we can do a
    // walk in the tree and only add O(log N) compressed edges. This solution
    // can be implemented in O(N^2 log N), but won't be very clean.

    vector<vector<array<int, 2>>> dist(n, vector<array<int, 2>>(n, {-1, -1}));
    vector<vector<pair<int, int>>> bucket(m + 1);

    int start_x = 0, start_y = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(tbl[i][j] == 'Q') {
                start_x = i;
                start_y = j;
                tbl[i][j] = '.';
            }
        }
    }

    dist[start_x][start_y][0] = 0;
    bucket[0].push_back({start_x, start_y});

    for(int d = 0; d < m; d++) {
        int p1 = (d + 1) & 1, p2 = d & 1;
        for(auto [x, y]: bucket[d]) {
            if(dist[x][y][d & 1] != d) {
                continue;
            }

            for(auto [dx, dy]: DIRS) {
                int bx = x - dx, by = y - dy;
                bool can_bounce =
                    (bx >= 0 && by >= 0 && bx < n && by < n &&
                     tbl[bx][by] != 'W');
                bool try1 = true, try2 = (d + 2 <= m);

                for(int xx = x + dx, yy = y + dy;
                    (try1 || try2) && xx >= 0 && yy >= 0 && xx < n && yy < n;
                    xx += dx, yy += dy) {
                    char cell = tbl[xx][yy];
                    if(cell == 'W') {
                        break;
                    }

                    if(try1) {
                        if(dist[xx][yy][p1] == -1) {
                            dist[xx][yy][p1] = d + 1;
                            bucket[d + 1].push_back({xx, yy});
                        } else if(dist[xx][yy][p1] <= d - 1) {
                            try1 = false;
                        }
                    }

                    if(try2 && can_bounce) {
                        if(dist[xx][yy][p2] == -1) {
                            dist[xx][yy][p2] = d + 2;
                            bucket[d + 2].push_back({xx, yy});
                        } else if(dist[xx][yy][p2] <= d) {
                            try2 = false;
                        }
                    }
                    can_bounce = true;

                    if(cell == 'B') {
                        break;
                    }
                }
            }
        }
    }

    int cnt = 0, ans = 0;
    int mp = m & 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(dist[i][j][mp] != -1) {
                ans++;
                cnt++;
            } else if(dist[i][j][mp ^ 1] != -1) {
                cnt++;
            }
        }
    }

    if(m > 0 && cnt == 1) {
        cout << 0 << '\n';
    } else {
        cout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

DIRS = [(-1, -1), (-1, 0), (-1, 1),
        ( 0, -1),          ( 0, 1),
        ( 1, -1), ( 1, 0), ( 1, 1)]

def solve() -> None:
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    board = [list(next(it)) for _ in range(n)]

    # Find queen; treat its square as empty.
    sx = sy = -1
    for i in range(n):
        for j in range(n):
            if board[i][j] == 'Q':
                sx, sy = i, j
                board[i][j] = '.'

    # dist[x][y][p] = minimal moves to reach (x,y) with parity p; -1 if unreachable.
    dist = [[[-1, -1] for _ in range(n)] for __ in range(n)]

    # Buckets for BFS by distance (0..m).
    buckets = [[] for _ in range(m + 1)]
    dist[sx][sy][0] = 0
    buckets[0].append((sx, sy))

    for d in range(m):
        p_next = (d + 1) & 1  # parity after 1 move
        p_same = d & 1        # parity after 2 moves is same as d

        for x, y in buckets[d]:
            # Skip stale entries
            if dist[x][y][d & 1] != d:
                continue

            for dx, dy in DIRS:
                # Can we bounce immediately in this direction?
                bx, by = x - dx, y - dy
                can_bounce = (0 <= bx < n and 0 <= by < n and board[bx][by] != 'W')

                try1 = True              # still try relaxations to d+1
                try2 = (d + 2 <= m)      # still try relaxations to d+2

                xx, yy = x + dx, y + dy
                while (try1 or try2) and 0 <= xx < n and 0 <= yy < n:
                    cell = board[xx][yy]

                    # White blocks completely
                    if cell == 'W':
                        break

                    # Relax to d+1
                    if try1:
                        if dist[xx][yy][p_next] == -1:
                            dist[xx][yy][p_next] = d + 1
                            buckets[d + 1].append((xx, yy))
                        elif dist[xx][yy][p_next] <= d - 1:
                            # Prune further d+1 relaxations along this ray
                            try1 = False

                    # Relax to d+2 (same parity) if a bounce is possible
                    if try2 and can_bounce:
                        if dist[xx][yy][p_same] == -1:
                            dist[xx][yy][p_same] = d + 2
                            buckets[d + 2].append((xx, yy))
                        elif dist[xx][yy][p_same] <= d:
                            # Prune further d+2 relaxations along this ray
                            try2 = False

                    # After at least one step, bouncing is possible
                    can_bounce = True

                    # Stop after capturing a black piece
                    if cell == 'B':
                        break

                    xx += dx
                    yy += dy

    mp = m & 1
    ans = 0
    reachable_any = 0

    for i in range(n):
        for j in range(n):
            if dist[i][j][mp] != -1:
                ans += 1
                reachable_any += 1
            elif dist[i][j][mp ^ 1] != -1:
                reachable_any += 1

    # If m>0 and nowhere to move (only start reachable), exactly m moves is impossible
    if m > 0 and reachable_any == 1:
        print(0)
    else:
        print(ans)

if __name__ == "__main__":
    solve()
```

