题解

这是一道博弈问题。双方轮流操作，马尼每天可以新建一堵墙（不能在哈米德当前位置），哈米德每天可以选择左或右，如果该方向无墙则逃脱，否则移动到最近墙并摧毁它。哈米德希望最小化逃脱天数，马尼希望最大化。我们需要求出双方均采取最优策略时的天数。

定义

设哈米德初始位置为 $x$。在初始网格中：

• $L$ 表示 $x$ 左侧最近的墙的位置（$1 \le L < x$），若左侧没有墙则 $L=0$。
• $R$ 表示 $x$ 右侧最近的墙的位置（$x < R \le n$），若右侧没有墙则 $R=n+1$。

最优策略分析

首先考虑哈米德的逃逸过程。如果他固定朝一个方向前进，马尼的最佳应对是每次在哈米德移动方向的前方紧邻位置建墙，迫使哈米德每天只能前进一格并摧毁一堵墙。在这种情况下：

• 若哈米德一直向左，从 $x$ 逃出左边界需要 $x$ 天（每天向左移动一格）。
• 若哈米德一直向右，从 $x$ 逃出右边界需要 $n-x+1$ 天（同理）。

但上述情况假设马尼从一开始就在那个方向紧挨着建墙。实际上，初始时已有墙存在，这会影响哈米德第一天的移动选择。

在第一天，马尼先行动，他可以建一堵新墙。他的最优选择只有两种有意义的情况：

1. 在 $x-1$ 处建墙（若该格为空且 $\ge 1$），这使得左侧最近墙变为 $x-1$。
2. 在 $x+1$ 处建墙（若该格为空且 $\le n$），这使得右侧最近墙变为 $x+1$。

如果选择方案 1，则：

• 若哈米德之后一直向左，需要 $x$ 天。
• 若哈米德之后一直向右，需要 $n - R + 2$ 天（解释见后）。 哈米德会选择天数较少的方向，因此这种情况下最终天数为 $\min(x, n - R + 2)$。

如果选择方案 2，则：

• 向左需要 $L + 1$ 天。
• 向右需要 $n - x + 1$ 天。 最终天数为 $\min(L + 1, n - x + 1)$。

马尼可以选择方案 1 或方案 2（如果都可行），他当然会选择使最终天数更大的那一个。因此答案为：

$$ans = \max\big( \min(x, \, n - R + 2), \; \min(L + 1, \, n - x + 1) \big) $$

如果某一侧原本就无法建墙（例如 $x=1$ 或 $x=n$ 或目标位置已经是墙），对应的那个表达式仍然兼容于公式。

向右逃生需要 $n - R + 2$ 天的推导

假设哈米德一直向右，初始右侧最近墙在 $R$。第一天他向右移动到 $R$ 并摧毁墙，花费 $1$ 天，位置变为 $R$。此后马尼每天在哈米德当前位置 $+1$ 处建墙（若该位置为空且 $\le n$），哈米德每天向右移动一格并摧毁墙。当哈米德到达位置 $n$ 时，右侧不再有墙，他可以在当天选择向右直接逃脱。从 $R$ 到达 $n$ 需要移动 $n - R$ 次（每次 $1$ 天），到达 $n$ 后再花 $1$ 天逃脱。总天数为 $1 + (n - R) + 1 = n - R + 2$。若初始 $R = n$，则第一天到 $n$，第二天逃脱，总天数 $2 = n - n + 2$，公式成立。若初始 $R = n+1$（右侧无墙），则 $n - R + 2 = 1$，实际上他可以第一天直接向右逃脱（$1$ 天），公式依然正确。

向左逃生需要 $L + 1$ 天的推导

对称地，若哈米德一直向左且马尼不干预初始 $L$（即马尼没有在 $x-1$ 建墙），则天数由 $L$ 决定。第一天他向左移动到 $L$（若 $L>0$）并摧毁墙，花费 $1$ 天，位置变 $L$。此后马尼每天在 $L-1, L-2, \dots$ 建墙，哈米德每天向左移动一格。从 $L$ 向左直到位置 $1$，再花 $1$ 天逃脱。总天数为 $1 + (L - 1) + 1 = L + 1$。若 $L = 0$（无墙），则第一天直接向左逃脱，$1$ 天，$L+1=1$，公式成立。

算法实现

对每组数据，只需要扫描字符串找到初始的 $L$ 和 $R$：

• 从 $x$ 向左遍历，找到第一个 # 的位置作为 $L$，若找不到则 $L = 0$。
• 从 $x$ 向右遍历，找到第一个 # 的位置作为 $R$，若找不到则 $R = n + 1$。

然后直接根据公式计算答案即可。每组数据的时间复杂度为 $O(n)$，总复杂度 $O(\sum n)$，可以承受 $2 \times 10^5$ 的数据规模。

代码参考

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

void solve() {
    int n, x;
    cin >> n >> x;
    string s;
    cin >> s;
    s = " " + s; // 让索引从 1 开始

    int L = 0, R = n + 1;
    for (int i = x - 1; i >= 1; i--) {
        if (s[i] == '#') {
            L = i;
            break;
        }
    }
    for (int i = x + 1; i <= n; i++) {
        if (s[i] == '#') {
            R = i;
            break;
        }
    }

    int ans = max(min(x, n - R + 2), min(L + 1, n - x + 1));
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}