当前没有测试数据。

题目背景 2024 年 9 月 GESP C++ 七级编程第 2 题

题目描述 ⼩杨有⼀个有⼀个 � × � n×m 的矩阵，仅包含 01 ? 01? 三种字符。矩阵的⾏从上到下编号依次为 1 , 2 , . . . , � 1,2,...,n，列从左到右编号依次为 1 , 2 , . . . 1,2,... , � m 编号。⼩杨开始在矩阵的左上角（ 1 , 1 1,1），⼩杨只能向下或者向右移动，最终到达右下角（ � , � n,m）时停⽌，在移动的过程中每经过⼀个字符 1 1 得分会增加⼀分（包括起点和终点），经过其它字符则分数不变。⼩杨的初始分数为 0 0 分。

⼩杨可以将矩阵中不超过 � x 个字符 ? ? 变为字符 1 1 。⼩杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道⾃⼰最多能获得多少分。

输入格式 第⼀⾏包含⼀个正整数 � t ，代表测试⽤例组数。

接下来是 � t 组测试⽤例。对于每组测试⽤例，⼀共 � + 1 n+1 ⾏。

第⼀⾏包含三个正整数 � , � , � n,m,x，含义如题⾯所⽰。

之后 � n ⾏，每⾏包含⼀个长度为 � m 且仅包含 01 ? 01? 三种字符的字符串。

输出格式 对于每组测试⽤例，输出⼀⾏⼀个整数，代表最优策略下⼩杨的得分最多是多少。

样例1 输入数据 1 2 3 3 1 000 111 01? 3 3 1 000 ?0? 01? 输出数据 1 4 2 样例解释 对于第⼆组测试⽤例，将（ 1 , 1 1,1）或者 （ 3 , 3 3,3）变成 1 1 均是最优策略。

数据范围 子任务编号 数据点占比 � t � , � n,m � x 1 30 % 30% ≤ 5 ≤5 ≤ 10 ≤10

1 =1 2 30 % 30% ≤ 10 ≤10 ≤ 500 ≤500 ≤ 30 ≤30 3 40 % 40% ≤ 10 ≤10 ≤ 500 ≤500 ≤ 300 ≤300 对于全部数据，保证有 1 ≤ � ≤ 10 1≤t≤10， 1 ≤ � , � ≤ 500 , 1 ≤ � ≤ 300 1≤n,m≤500,1≤x≤300，同时保证所有测试⽤例 � × � n×m 的总和不超过 2.5 × 1 0 5 2.5×10 5 。