p235.in1
======================
3
2
Q..
...
...

=================
p235.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;
}

=================
p235.ans1
======================
9

=================
statement.txt
======================
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

=================
