#2284. [GESP202409 七级] 矩阵移动
[GESP202409 七级] 矩阵移动
Description
⼩杨有⼀个有⼀个 的矩阵,仅包含 三种字符。矩阵的⾏从上到下编号依次为 ,列从左到右编号依次为 , 编号。⼩杨开始在矩阵的左上角( ),⼩杨只能向下或者向右移动,最终到达右下角()时停⽌,在移动的过程中每经过⼀个字符 得分会增加⼀分(包括起点和终点),经过其它字符则分数不变。⼩杨的初始分数为 分。
⼩杨可以将矩阵中不超过 个字符 变为字符 。⼩杨在修改矩阵后,会以最优的策略从左上角移动到右下角。他想知道⾃⼰最多能获得多少分。
Input Format
第⼀⾏包含⼀个正整数 ,代表测试⽤例组数。
接下来是 组测试⽤例。对于每组测试⽤例,⼀共 ⾏。
第⼀⾏包含三个正整数 ,含义如题⾯所⽰。
之后 ⾏,每⾏包含⼀个长度为 且仅包含 三种字符的字符串。
Output Format
对于每组测试⽤例,输出⼀⾏⼀个整数,代表最优策略下⼩杨的得分最多是多少。
2
3 3 1
000
111
01?
3 3 1
000
?0?
01?
4
2
Hint
样例解释
对于第⼆组测试⽤例,将()或者 ()变成 均是最优策略。
数据范围
子任务编号 | 数据点占比 | |||
---|---|---|---|---|
1 | ||||
2 | ||||
3 |
对于全部数据,保证有 ,,同时保证所有测试⽤例 的总和不超过 。
Source
GESP七级202409