## 1) Concise abridged problem statement

Given an \(N \times N\) board (\(2 \le N \le 300\)) with cells 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 chess queen (any number of squares in 8 directions). It **cannot pass through** any piece. It may **land on** a black piece square (capture), but then cannot move beyond it in the same move.

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

---

## 2) Detailed editorial (explaining the given solution)

### Key observations

1. **Movement graph**
   Each board cell is a node. From a cell \((x,y)\), the queen can move in each of 8 directions until it hits:
   - board boundary (stop),
   - a white piece `W` (blocked, cannot enter, stop),
   - a black piece `B` (can enter/capture, but stop after entering).

2. **Exactly \(M\) moves vs. “at most \(M\)”**
   We need positions reachable in *exactly* \(M\) queen moves.

   A typical trick: if we can “waste” moves in cycles, then once a cell is reachable, it might also be reachable in more moves with the same parity.

3. **Parity matters (distance modulo 2)**
   The solution relies on this idea:
   - If a cell is reachable in \(d\) moves, often it is also reachable in \(d+2\) moves by doing a 2-move “bounce” (move somewhere and come back or equivalent).
   - Therefore, for each cell we track the **minimum number of moves to reach it with even parity** and **with odd parity**.

   We then answer:
   \[
   \#\{(i,j) \mid \text{minDist}[i][j][M\%2] \neq -1 \text{ and } \text{minDist}[i][j][M\%2] \le M\}.
   \]

4. **Why do we also propagate “+2” edges? (bounce behind / wall bounce)**
   When moving along a ray, a 2-move waste is possible if the queen can “bounce”:
   - If behind the queen (opposite direction) is either outside the board or blocked by a **non-white** cell, the bounce might not be possible immediately.
   - The code carefully models whether a “bounce” is possible by checking the square behind the start, and then after moving at least one step, bounce becomes possible (`can_bounce = true`), because you can always go back to the previous square (unless blocked by `W`, which would have stopped you already).

   The implementation adds two kinds of relaxations while scanning each ray:
   - Reach \((xx,yy)\) in **\(d+1\)** moves (normal move).
   - Reach \((xx,yy)\) in **\(d+2\)** moves **with same parity as \(d\)**, if bounce is possible.

5. **BFS by move count using buckets**
   Since \(M \le 50\), we can do BFS layered by exact distance with an array of vectors:
   - `bucket[d]` holds all states first discovered at distance `d`.
   - Relaxations only go to `d+1` and `d+2`, so this is easy.

6. **Early stopping along a ray (performance)**
   Scanning can be expensive (\(O(N)\) per direction per visited cell), so the code includes pruning:
   - If we find a cell already reachable with same parity at a distance \(\le d-1\), then pushing further `d+1` updates along that ray won’t improve anything (“try1 = false”).
   - Similarly for the `d+2` parity case.

   Overall complexity is roughly \(O(M \cdot N^3)\) worst-case, but with small \(M\) and pruning it is intended to pass.

7. **Special case when no move is possible**
   If \(M>0\) and the queen cannot reach any other cell in any parity (only the start is reachable), then the answer should be 0 (you cannot “wait” in place; every move must change the position).
   The code computes:
   - `cnt` = number of cells reachable with either parity,
   - if `cnt == 1` (only the starting cell) and `M>0`, print 0.

---

## 3. C++ Solution

```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;
}
```

---

## 4) Python solution (same approach, with 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().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    board = [list(next(it)) for _ in range(n)]

    # Locate the queen and treat its start as empty for movement purposes.
    sx = sy = 0
    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] = minimum moves to reach (x,y) with parity p, else -1.
    dist = [[[-1, -1] for _ in range(n)] for __ in range(n)]

    # Buckets for BFS layers by exact move count (0..m).
    buckets = [[] for _ in range(m + 1)]

    dist[sx][sy][0] = 0
    buckets[0].append((sx, sy))

    # Process distances 0..m-1 and relax to d+1 and d+2 where possible.
    for d in range(m):
        p1 = (d + 1) & 1  # parity after 1 move
        p2 = d & 1        # parity after 2 moves (same parity)

        for x, y in buckets[d]:
            # Skip stale entries (if later we found a shorter distance of same parity).
            if dist[x][y][d & 1] != d:
                continue

            for dx, dy in DIRS:
                # Check if an immediate bounce is possible from the starting square
                # along this direction (requires the behind cell to exist and not be 'W').
                bx, by = x - dx, y - dy
                can_bounce = (0 <= bx < n and 0 <= by < n and board[bx][by] != 'W')

                try1 = True
                try2 = (d + 2 <= m)

                xx, yy = x + dx, y + dy
                # Scan along the ray while within bounds and at least one relaxation is active.
                while (try1 or try2) and 0 <= xx < n and 0 <= yy < n:
                    cell = board[xx][yy]

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

                    # Relax distance d+1
                    if try1:
                        if dist[xx][yy][p1] == -1:
                            dist[xx][yy][p1] = d + 1
                            buckets[d + 1].append((xx, yy))
                        elif dist[xx][yy][p1] <= d - 1:
                            # Prune: further squares won't benefit for d+1 relaxations.
                            try1 = False

                    # Relax distance d+2 if bounce is possible
                    if try2 and can_bounce:
                        if dist[xx][yy][p2] == -1:
                            dist[xx][yy][p2] = d + 2
                            buckets[d + 2].append((xx, yy))
                        elif dist[xx][yy][p2] <= d:
                            # Prune for d+2 relaxations.
                            try2 = False

                    # After moving at least one step, we can bounce by returning
                    # to the previous square (since we didn't pass through a 'W').
                    can_bounce = True

                    # Black piece can be landed on, but blocks further scanning.
                    if cell == 'B':
                        break

                    xx += dx
                    yy += dy

    mp = m & 1
    ans = 0
    cnt_any = 0

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

    # If m>0 and only starting cell reachable at all, then no legal move exists.
    if m > 0 and cnt_any == 1:
        print(0)
    else:
        print(ans)

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

---

## 5) Compressed editorial

Model queen moves as transitions along 8 rays, stopping at `W` (cannot enter) and stopping after landing on `B` (capture). We need cells reachable in exactly \(M\) moves. Track for each cell the minimum number of moves to reach it with each parity (even/odd), since extra 2-move “wastes” can often be inserted. Run a BFS-like process by distance using buckets `bucket[d]`, relaxing to distance `d+1` for normal queen moves and also to `d+2` (same parity) when a 2-move bounce is feasible. Prune scanning along a ray when existing distances already dominate. Finally count cells with `dist[cell][M%2] != -1`. Special case: if \(M>0\) and no move exists (only start reachable at all), answer is 0.