题目背景

蓝桥学院的地下管线出现故障，小蓝派出巡线机器人沿管道巡检。管道是无限延伸的格子轨道，机器人从 0 号格子出发。指令包含：

指令	含义
L	向左移动一格
R	向右移动一格
S	停留在原地
?	数据损坏，需修复为 L、R 或 S

目标：选择最优修复方案，使机器人经过的不同格子数量最多。

---

输入输出

输入：一个字符串 T（1 ≤ |T| ≤ 10^5），由 L、R、S、? 组成

输出：最多能巡检的不同格子数

样例：

输入：L??R
输出：4

解释：两个 ? 都修复为 R，路径为 0 → -1 → 0 → 1 → 2，经过 {-1, 0, 1, 2} 共 4 个格子。

---

思路分析

第一步：排除无效选择

? 修复为 S（不动）毫无意义——不增加任何新格子。所以 ? 只会变成 L 或 R。

第二步：混合选择 vs 单向选择

假设有两个 ?，一个选 L、一个选 R：

路径折返：左走 → 右走 → 回到已访问区域

这样会在原地来回，浪费覆盖机会。

而全部选 L 或全部选 R：

路径单向延伸：一直往左 或 一直往右

每次移动都走向全新格子，覆盖最大化。

第三步：核心结论

最优策略：所有 ? 要么全变 L，要么全变 R，取两者覆盖范围的最大值。

---

代码实现

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

/**
 * 模拟机器人巡检过程
 * @param s 指令字符串
 * @param allRight true: 所有?变R向右；false: 所有?变L向左
 * @return 经过的不同格子数量
 */
long long calc(const string &s, bool allRight)
{
    long long x = 0;        // 当前位置
    long long minx = 0;     // 最左边界（初始在0）
    long long maxx = 0;     // 最右边界（初始在0）
    
    for (char c : s)
    {
        // 根据指令移动
        if (c == 'L') 
            x--;                    // 左移
        else if (c == 'R') 
            x++;                    // 右移
        else if (c == 'S') 
            {}                      // 不动
        else  // '?' 修复为 L 或 R
        {
            if (allRight) 
                x++;                // 全往右
            else 
                x--;                // 全往左
        }
        
        // 实时更新边界
        minx = min(minx, x);
        maxx = max(maxx, x);
    }
    
    // 覆盖格子数 = 最右 - 最左 + 1（包含两端）
    return maxx - minx + 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    long long ansR = calc(s, true);   // 所有 ? → R
    long long ansL = calc(s, false);  // 所有 ? → L
    
    cout << max(ansR, ansL) << endl;
    
    return 0;
}

---

代码图解

以 L??R 为例，全变 R 的执行过程：

步骤    指令    位置x    最左minx    最右maxx
─────────────────────────────────────────────
初始    -       0        0           0
1       L       -1       -1          0
2       ?→R     0        -1          0
3       ?→R     1        -1          1
4       R       2        -1          2
─────────────────────────────────────────────
结果：maxx - minx + 1 = 2 - (-1) + 1 = 4 ✓

---

为什么公式是 maxx - minx + 1？

最左位置              最右位置
   -1    0    1    2
    ●────●────●────●
    ↑              ↑
   起点           终点
    
格子数 = 2 - (-1) + 1 = 4
        └──┬──┘  └┘
          距离    包含两端

---

复杂度分析

项目	复杂度	说明
时间	O(n)	遍历两遍字符串
空间	O(1)	只用几个变量

轻松通过 n ≤ 10^5 的限制。

---

易错点总结

错误思路	原因
? 变 S	不移动，浪费机会，覆盖不会增加
? 混合选择（部分L部分R）	路径折返，重复访问已走过的格子
用 int 存位置	n = 10^5 时可能溢出，用 long long 保险

---

举一反三

这类"最优路径覆盖"问题的通用思路：

1. 排除无效操作（如本题中的 S）
2. 分析极端策略（全左 / 全右）
3. 证明最优性（混合策略不会更优）
4. 模拟取最值

---

完整代码（简洁版）

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

long long calc(const string &s, bool r) {
    long long x = 0, mn = 0, mx = 0;
    for (char c : s) {
        if (c == 'L') x--;
        else if (c == 'R') x++;
        else if (c == '?') x += r ? 1 : -1;
        mn = min(mn, x), mx = max(mx, x);
    }
    return mx - mn + 1;
}

int main() {
    string s; cin >> s;
    cout << max(calc(s, 1), calc(s, 0));
}

---

核心思想：贪心不一定复杂，有时候"走极端"就是最优解。