A7468 | 午枫的教室路线
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
小午所在的教室被划分成一个 $H \times W$ 的方格，每个格子表示一个座位。
小午从左上角座位 $(1,1)$ 出发，需要走到右下角座位 $(H,W)$。
每一步只能向下（D）或向右（R）移动一格，总共需要走 $H+W-2$ 步。
现在给定一个长度为 $H+W-2$ 的字符串 $S$，其中：
-
-
-
对于每一种合法的走法，小午都会把路径上经过的所有座位（包括起点和终点）都标记为“已访问”。
现在，小午想知道：
在所有满足 $S$ 约束的路径中，最多可以让多少个不同的座位被访问到（至少一次）。
小午从左上角座位 $(1,1)$ 出发，需要走到右下角座位 $(H,W)$。
每一步只能向下（D）或向右（R）移动一格，总共需要走 $H+W-2$ 步。
现在给定一个长度为 $H+W-2$ 的字符串 $S$，其中：
-
D 表示这一步必须向下走；-
R 表示这一步必须向右走；-
? 表示这一步可以自由选择向下或向右。对于每一种合法的走法，小午都会把路径上经过的所有座位（包括起点和终点）都标记为“已访问”。
现在，小午想知道：
在所有满足 $S$ 约束的路径中，最多可以让多少个不同的座位被访问到（至少一次）。
输入格式
第一行输入一个整数 $T$，表示测试数据组数。
对于每组数据：
第一行输入两个整数 $H,W$，表示教室的行数和列数。
第二行输入一个长度为 $H+W-2$ 的字符串 $S$，由
对于每组数据：
第一行输入两个整数 $H,W$，表示教室的行数和列数。
第二行输入一个长度为 $H+W-2$ 的字符串 $S$，由
D、R 和 ? 组成，表示移动规则。输出格式
对于每组数据，输出一行一个整数，表示最多可以被访问到的座位数量。
输入输出样例
输入 #1
4 4 5 D?DRR?R 4 5 DDRRDRR 4 5 ??????? 2 2 DR
输出 #1
12 8 20 3
【解释说明】
样例 1 解释
小午可以选择不同的“?”路径，使得走出的路径覆盖尽可能多的座位。
例如可以通过不同的走法组合，让多个路径的访问区域尽可能“分散”，最终总共覆盖 $12$ 个不同座位。
【数据范围】
对于 $100\%$ 的测试数据，满足：
$1 \le T \le 2 \times 10^5$
$2 \le H,W \le 2 \times 10^5$
字符串 $S$ 长度为 $H+W-2$
保证至少存在一种合法路径
单个测试中 $\sum (H+W) \le 4 \times 10^5$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？