Coi bảo tàng là đồ thị gồm ~n \times m~ đỉnh, mỗi ô tương ứng với một đỉnh và các cạnh tương ứng với các cặp hai ô trống kề nhau. Dễ dàng nhận thấy bảo tàng sẽ được chia thành các thành phần liên thông. Đánh số các thành phần liên thông đó.

Gọi ~cnt[i]~ là số bức tranh tối đa mà Igor có thể xem khi anh ấy đứng trong thành phần liên thông thứ ~i~. Với mỗi thành phần liên thông, ta sử dụng thuật toán DFS/BFS đếm xem thành phần hiện tại kề với bao nhiêu *. Kết quả cho mỗi truy vấn sẽ là ~cnt[id[x][y]]~ với ~id[x][y]~ là chỉ số thành phần liên thông chứa ô ~(x, y)~.

Độ phức tạp: ~O(n \times m + k)~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int n, m, k;
char a[N][N];
int cnt[N * N], id[N][N];

void dfs(int i, int j, int rt) {
    id[i][j] = rt;
    for (int t = 0; t < 4; ++t) {
        int u = i + dx[t], v = j + dy[t];
        if (a[u][v] == '*') cnt[rt]++;
        else if (!id[u][v]) dfs(u, v, rt);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) cin >> a[i][j];

    int rt = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j] == '*' || id[i][j]) continue;
            ++rt;
            dfs(i, j, rt);
        }
    }

    while (k--) {
        int x, y; cin >> x >> y;
        cout << cnt[id[x][y]] << '\n';
    }
    return 0;
}