解题思路

题意可抽象为：把 D 看作可行走的空地 .，隧道是由若干段连续的空地段（. 段）与障碍段（# 段）交替组成。 “轻松移动”就是在同一 . 段内左右走；一旦至少进行过一次轻松移动（即所在 . 段长度 ≥ 2），就可以“穿墙”越过紧邻在该段一侧的一整段 #，但穿墙需要从该 . 段的末端出发并且该端至少有两个连续的 .（正好是该段末尾的两个格），落点为墙另一侧的第一个 .。之后仍可继续走或继续穿下一堵墙。

因此，从包含 D 的那一段 .（记作区间 [L, R]）出发，有以下充要条件：

1. 若该段触达左边界（L==1）或右边界（R==n），直接走出即可，答案 YES。
2. 若该段长度为 1（R-L+1==1），无法进行任何“轻松移动”，也就不能启动穿墙，且不触边界时答案 NO。
3. 否则（该段长度 ≥ 2），可以选择向左或向右不断“穿一段墙 + 进入下一段 . 段”。 为使过程可持续，中间经过的每一段 .（不含最后触边界的那段）都必须长度 ≥ 2，否则无法从该段再度起跳穿过下一堵墙；如果某侧遇到的下一堵墙一直延伸到边界，则可直接穿到边界外（落到 0 或 n+1），立即成功。

据此我们只需在线性时间内自包含 D 的 . 段向左（或向右）交替跨过一段 # 并进入下一段 . 继续检查，直到：

• 触达边界（成功），或
• 进入长度为 1 且不触边界的 . 段（该方向失败）。 只要左右任一方向成功，即输出 YES。

算法要点（实现细节）：

• 先把 D 改成 .，并在两端添哨兵：位置 0 与 n+1 视作无障碍的“外部”。

• 线性扩展得到包含 D 的 . 段 [L, R]。

• 若不直接触边界且段长 ≥ 2，则分别尝试：

  • 向左：每次越过紧贴在 L 左侧的整段 #，落到左侧的下一段 .；若该 # 段顶到最左端（1），则此跳直接出界成功。
  • 向右：同理处理右侧。

• 每个格子至多被扫描常数次，总体 O(n)。

复杂度分析

• 时间复杂度：对每组数据仅做常数次线性扫描，整体 O(n)，并且满足题目保证的总长度 Σn ≤ 1e6。
• 空间复杂度：使用若干指针与常数辅助变量，O(1) 额外空间。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

def can_exit_one_side_left(a, n, L, R):
    """从包含 D 的 '.' 段 [L, R] 向左反复尝试穿墙"""
    left = L  # 当前所在 '.' 段的最左端
    while True:
        # 紧挨在该段左侧的 '#' 段：其右端是 left-1
        bL = left - 1  # 当前 '#' 段的左端（待回溯求）
        # 回溯到这段 '#' 的最左端
        while bL - 1 >= 1 and a[bL - 1] == '#':
            bL -= 1
        # 若这段墙一直顶到位置 1，则可直接穿到 0，成功
        if bL == 1:
            return True
        # 墙的左侧必有一段 '.'，其右端为 bL-1，向左扩展得到该 '.' 段
        runR = bL - 1
        runL = runR
        while runL - 1 >= 1 and a[runL - 1] == '.':
            runL -= 1
        # 若该 '.' 段触达左边界，直接走出成功
        if runL == 1:
            return True
        # 中间段必须长度 ≥ 2，才能再次从其左端起跳穿下一堵墙
        if runR - runL + 1 >= 2:
            left = runL  # 进入这段 '.'，继续循环
        else:
            return False  # 段长为 1 且不触边界，卡住

def can_exit_one_side_right(a, n, L, R):
    """从包含 D 的 '.' 段 [L, R] 向右反复尝试穿墙"""
    right = R  # 当前所在 '.' 段的最右端
    while True:
        # 紧挨在该段右侧的 '#' 段：其左端是 right+1
        bR = right + 1  # 当前 '#' 段的右端（待前进求）
        # 前进到这段 '#' 的最右端
        while bR + 1 <= n and a[bR + 1] == '#':
            bR += 1
        # 若这段墙一直顶到位置 n，则可直接穿到 n+1，成功
        if bR == n:
            return True
        # 墙的右侧必有一段 '.'，其左端为 bR+1，向右扩展得到该 '.' 段
        runL = bR + 1
        runR = runL
        while runR + 1 <= n and a[runR + 1] == '.':
            runR += 1
        # 若该 '.' 段触达右边界，直接走出成功
        if runR == n:
            return True
        # 中间段必须长度 ≥ 2，才能再次从其右端起跳穿下一堵墙
        if runR - runL + 1 >= 2:
            right = runR  # 进入这段 '.'，继续循环
        else:
            return False  # 段长为 1 且不触边界，卡住

def solve_one(n, s):
    # 建立 1..n 的数组并把 D 当作 '.'
    a = ['.'] * (n + 2)  # a[0] 与 a[n+1] 作为哨兵'.'
    d = -1
    for i, ch in enumerate(s, 1):
        if ch == 'D':
            a[i] = '.'
            d = i
        else:
            a[i] = ch
    # 找到包含 d 的 '.' 段 [L, R]
    L = d
    while L - 1 >= 1 and a[L - 1] == '.':
        L -= 1
    R = d
    while R + 1 <= n and a[R + 1] == '.':
        R += 1
    # 情况 1：直接触边界
    if L == 1 or R == n:
        return True
    # 情况 2：段长为 1，无法启动穿墙
    if R - L + 1 == 1:
        return False
    # 情况 3：尝试向左或向右序贯穿墙
    if can_exit_one_side_left(a, n, L, R):
        return True
    if can_exit_one_side_right(a, n, L, R):
        return True
    return False

def main():
    data = sys.stdin.buffer.read().splitlines()
    it = iter(data)
    T = int(next(it).strip())
    out = []
    for _ in range(T):
        n = int(next(it).strip())
        s = next(it).strip().decode()
        out.append("YES" if solve_one(n, s) else "NO")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名 Main
// 思路同上：把 D 当作 '.'，线性扩展所在 '.' 段，若不直接触边界且段长≥2，
// 则向左/向右交替越过一整段 '#' 并进入下一段 '.'，中间所有 '.' 段长度必须≥2。
import java.io.*;
import java.util.*;

public class Main {
    // 向左尝试穿墙直到出界或卡住
    static boolean goLeft(char[] a, int n, int L, int R) {
        int left = L;
        while (true) {
            // 紧邻左侧的 '#' 段右端为 left-1，回溯到其左端
            int bL = left - 1;
            while (bL - 1 >= 1 && a[bL - 1] == '#') bL--;
            // 若墙贴到 1，直接穿到 0
            if (bL == 1) return true;
            // 墙左侧的 '.' 段：右端 bL-1，向左扩展
            int runR = bL - 1;
            int runL = runR;
            while (runL - 1 >= 1 && a[runL - 1] == '.') runL--;
            // 若该 '.' 段触达左边界，直接走出
            if (runL == 1) return true;
            // 中间 '.' 段必须长度 ≥ 2
            if (runR - runL + 1 >= 2) {
                left = runL; // 进入该段，继续
            } else {
                return false; // 段长为 1 且不触边界，卡住
            }
        }
    }

    // 向右尝试穿墙直到出界或卡住
    static boolean goRight(char[] a, int n, int L, int R) {
        int right = R;
        while (true) {
            // 紧邻右侧的 '#' 段左端为 right+1，前进到其右端
            int bR = right + 1;
            while (bR + 1 <= n && a[bR + 1] == '#') bR++;
            // 若墙贴到 n，直接穿到 n+1
            if (bR == n) return true;
            // 墙右侧的 '.' 段：左端 bR+1，向右扩展
            int runL = bR + 1;
            int runR = runL;
            while (runR + 1 <= n && a[runR + 1] == '.') runR++;
            // 若该 '.' 段触达右边界，直接走出
            if (runR == n) return true;
            // 中间 '.' 段必须长度 ≥ 2
            if (runR - runL + 1 >= 2) {
                right = runR; // 进入该段，继续
            } else {
                return false; // 段长为 1 且不触边界，卡住
            }
        }
    }

    static boolean solveOne(int n, String s) {
        // a[0] 与 a[n+1] 作为哨兵 '.'
        char[] a = new char[n + 2];
        Arrays.fill(a, '.');
        int d = -1;
        for (int i = 1; i <= n; i++) {
            char ch = s.charAt(i - 1);
            if (ch == 'D') {
                a[i] = '.';
                d = i;
            } else {
                a[i] = ch;
            }
        }
        // 扩展包含 d 的 '.' 段 [L, R]
        int L = d, R = d;
        while (L - 1 >= 1 && a[L - 1] == '.') L--;
        while (R + 1 <= n && a[R + 1] == '.') R++;
        // 触边界直接成功
        if (L == 1 || R == n) return true;
        // 段长为 1 无法启动穿墙
        if (R - L + 1 == 1) return false;
        // 左或右任一方向可成功
        if (goLeft(a, n, L, R)) return true;
        if (goRight(a, n, L, R)) return true;
        return false;
    }

    // 简单高效的输入读取
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-' ) { sgn = -1; c = read(); }
            for (; c > ' '; c = read()) x = x * 10 + (c - '0');
            return x * sgn;
        }
        String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder();
            // 跳过行首换行
            while (true) {
                c = read();
                if (c == -1) return sb.length() == 0 ? null : sb.toString();
                if (c != '\n' && c != '\r') { sb.append((char)c); break; }
            }
            // 读到行尾
            while (true) {
                c = read();
                if (c == -1 || c == '\n' || c == '\r') break;
                sb.append((char)c);
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int T = fs.nextInt();
        StringBuilder out = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            int n = fs.nextInt();
            String s = fs.nextLine();
            // 若上一行读完整后紧跟下一行为空，应再读一次
            while (s == null || s.length() == 0) s = fs.nextLine();
            out.append(solveOne(n, s) ? "YES" : "NO").append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

// 思路同上：把 D 当作 '.'，线性扩展所在 '.' 段；若段长≥2则可向某侧依次“穿一堵墙+进入下一段 '.'”。
// 中间所有 '.' 段必须长度≥2；若遇到墙贴边界可直接穿到界外成功。
#include <bits/stdc++.h>
using namespace std;

bool goLeft(const vector<char>& a, int n, int L, int R) {
    int left = L;
    while (true) {
        int bL = left - 1;                 // 紧邻 '#' 段的右端
        while (bL - 1 >= 1 && a[bL - 1] == '#') bL--; // 回溯到该 '#' 段左端
        if (bL == 1) return true;          // 墙贴到 1，可直接穿到 0
        int runR = bL - 1;                 // 墙左侧 '.' 段右端
        int runL = runR;
        while (runL - 1 >= 1 && a[runL - 1] == '.') runL--; // 扩展该 '.' 段
        if (runL == 1) return true;        // 触达左边界，直接走出
        if (runR - runL + 1 >= 2) {
            left = runL;                   // 中间段长度≥2，可继续
        } else {
            return false;                  // 段长为 1 且不触边界，卡住
        }
    }
}

bool goRight(const vector<char>& a, int n, int L, int R) {
    int right = R;
    while (true) {
        int bR = right + 1;                // 紧邻 '#' 段左端
        while (bR + 1 <= n && a[bR + 1] == '#') bR++; // 前进到该 '#' 段右端
        if (bR == n) return true;          // 墙贴到 n，可直接穿到 n+1
        int runL = bR + 1;                 // 墙右侧 '.' 段左端
        int runR = runL;
        while (runR + 1 <= n && a[runR + 1] == '.') runR++; // 扩展该 '.' 段
        if (runR == n) return true;        // 触达右边界，直接走出
        if (runR - runL + 1 >= 2) {
            right = runR;                  // 中间段长度≥2，可继续
        } else {
            return false;                  // 段长为 1 且不触边界，卡住
        }
    }
}

bool solveOne(int n, const string& s) {
    vector<char> a(n + 2, '.'); // a[0], a[n+1] 作为哨兵 '.'
    int d = -1;
    for (int i = 1; i <= n; ++i) {
        char ch = s[i - 1];
        if (ch == 'D') { a[i] = '.'; d = i; }
        else a[i] = ch;
    }
    int L = d, R = d;                    // 扩展包含 d 的 '.' 段
    while (L - 1 >= 1 && a[L - 1] == '.') --L;
    while (R + 1 <= n && a[R + 1] == '.') ++R;
    if (L == 1 || R == n) return true;   // 直接触边界
    if (R - L + 1 == 1) return false;    // 段长为 1，无法启动穿墙
    if (goLeft(a, n, L, R)) return true; // 左侧可出
    if (goRight(a, n, L, R)) return true;// 右侧可出
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; string s;
        cin >> n >> s;
        cout << (solveOne(n, s) ? "YES" : "NO") << '\n';
    }
    return 0;
}

题目内容

多多在一个长为 $n$ 的横向隧道里，隧道每个位置用 $1$ 到 $n$ 的整数表示。

如果多多当前位置为 $x$ ，且他的左边(或右边)一个位置没有障碍物，则他可以轻松移动到 $x-1$ (或 $x+1$ )的位置。

多多还有一个"穿墙"的技能：如果他至少进行了一次轻松的移动,则他可以穿过原移动方向上的一段连续障碍物，并停留在这段障碍物的下一个位置。

形式化地说，如果在隧道区间 $[l,r]$ 内存在一段连续的障碍物，且 $l-2,l-1,r+1$(或 $l-1,r+1,r+2$) 位置无障碍物，则多多可以从 $l-2$ (或 $r+2$) 处出发穿墙并最终停留在 $r+1$ (或 $l-1$ )处。

给定隧道内障碍物的分布，问多多最终能否穿出隧道?

输入描述

第一行为一个整数 $T(1≤T≤10^6)$ ，表示接下来有 $T$ 组数据据。每组数据第一行为一个整数 $n(1≤n≤10^6)$ 表示表示隧道的长度，第二行为一个长度为 $n$ 的字符串，字符串由 "#","$D$" 组成，第 $i$ 个字符为 "#" 表示隧道的第 $i$ 个位置存在障碍物，'$.$' 表示空地(无障碍物)，'$D$' 即多多所在的初始位置。

数据保证 $\sum n≤10^6$，且每个字符串有且仅有一个字符串为 '$D$' 。

输出描述

若多多可以从初始位置到达位置 $0$ 或者 $n+1$ (即穿出隧道，这两个位置均无障碍物)，则输出"$YES$”，否则输出 $NO$”，每组数据对应一行输出。

样例1

输入

4
5
##D##
5
..D.#
7
#.#.D##
5
D####

输出

NO
YES
YES
YES

说明

第一组数据多多在第 $3$ 个位置动弹不得，无法穿出隧道、输出 $NO$ 。

第二组数据多多可以从左边一路走出随道，或者向右经过一次“轻松”的移动再穿墙而出。

第三组数据多多可以先向左走一步，再从右边穿墙而出。

第四组数据多多只能从左边走出隧道。