题意概括

在一个 $n \times m$ 的网格博物馆中，单元格要么是空（.）要么是不可通行（*），且边界全为不可通行。每对相邻的不同类型单元格之间有一堵墙，墙上挂有一幅画。Igor 起始于某个空单元格，能沿着空单元格四连通移动。他可以看到所有与他所在空单元格相邻的墙上的画（即与该空单元格相邻的不可通行单元格所对应的墙）。由于他可以在连通块内任意移动，实际上他能看到整个连通块内所有空单元格相邻的墙上的画的总数。题目给出多个起始位置，要求对每个起始位置输出从该位置出发能看到的最大画的数量。

样例分析

样例 1

输入：

5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

网格如下（行列编号从 1 开始）：

1: ******
2: *..*.*
3: ******
4: *....*
5: ******

起始 (2, 2)：该单元格为 .，所在连通块由第 2 行的 (2,2) 和 (2,3) 两个 . 组成。计数与它们相邻的 *：

• (2,2) 相邻的 *：上(1,2)、下(3,2)、左(2,1)，共 3 个。
• (2,3) 相邻的 *：上(1,3)、下(3,3)、右(2,4)，共 3 个。 总图画数量 = 3 + 3 = 6。输出第一行为 6。

起始 (2, 5)：该单元格为 .，是一个孤立的空单元格，相邻有上(1,5)、下(3,5)、左(2,4)、右(2,6) 四个 *。总图画数量 = 4。输出 4。

起始 (4, 3)：该单元格在第 4 行 *....* 中，连通块包含 (4,2)、(4,3)、(4,4)、(4,5) 四个 .。分别计数相邻 *：

• (4,2)：上(3,2)、下(5,2)、左(4,1) → 3 个。
• (4,3)：上(3,3)、下(5,3) → 2 个。
• (4,4)：上(3,4)、下(5,4) → 2 个。
• (4,5)：上(3,5)、下(5,5)、右(4,6) → 3 个。 总和 = 3+2+2+3 = 10。输出 10。

最终输出：

6
4
10

样例 2

输入：

4 4 1
****
*..*
*.**
****
3 2

网格：

1: ****
2: *..*
3: *.**
4: ****

起始 (3,2)：该单元格为 .，连通块包含 (2,2)、(2,3)、(3,2) 三个 .。计数相邻 *：

• (2,2)：上(1,2)、左(2,1) → 2 个。
• (2,3)：上(1,3)、下(3,3)、右(2,4) → 3 个。
• (3,2)：下(4,2)、左(3,1)、右(3,3) → 3 个。 总和 = 2 + 3 + 3 = 8。输出 8。

算法分析

1. 将网格中所有连通的空单元格（.）划分为不同的连通分量（使用 BFS 或 DFS 进行 Flood Fill）。
2. 在遍历每个连通分量时，对于访问到的每一个空单元格，检查其四方向相邻的单元格。若相邻单元格为不可通行（*），则该分量看到的画的数量加 1。
3. 每个连通分量分配一个唯一编号，并记录该分量对应的画的总数。
4. 对于每一个询问的起始位置 (x, y)（保证是空单元格），直接查表输出其所在连通分量的画的总数。

由于每个相邻的 . 和 * 构成一堵独立的墙，按上述方法统计不会重复也不会遗漏。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    vector<vector<int>> comp(n, vector<int>(m, -1));
    vector<int> comp_pics;
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '.' && comp[i][j] == -1) {
                int cur_id = comp_pics.size();
                comp_pics.push_back(0);
                queue<pair<int,int>> q;
                q.push({i, j});
                comp[i][j] = cur_id;
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                            if (grid[nx][ny] == '*') {
                                comp_pics[cur_id]++;
                            } else if (grid[nx][ny] == '.') {
                                if (comp[nx][ny] == -1) {
                                    comp[nx][ny] = cur_id;
                                    q.push({nx, ny});
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        int id = comp[x][y];
        cout << comp_pics[id] << '\n';
    }
    return 0;
}

复杂度

时间复杂度：$O(nm + k)$，其中 $nm$ 为网格大小，$k$ 为询问次数。
空间复杂度：$O(nm)$，用于存储网格、连通分量编号以及各分量的图画数量。