A71636 | $矩阵移动（matrix）$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

小杨有一个 n \times m的矩阵，仅包含 01? 三种字符。矩阵的行从上到下编号依次为 1,2,\dots,n，列从左到右编号依次为 1,2,\dots,m 编号。小杨开始在矩阵的左上角（1,1 ），小杨只能向下或者向右移动，最终到达右下角（ n,m）时停止，在移动的过程中每经过一个字符 1 得分会增加一分（包括起点和终点），经过其它字符则分数不变。小杨的初始分数为 0 分。 小杨可以将矩阵中不超过 x 个字符 ? 变为字符 1。小杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。

输入格式

第一行包含一个正整数 t ，代表测试用例组数。 接下来是 t 组测试用例。对于每组测试用例，一共 n+1 行。 第一行包含三个正整数 n,m,x ，含义如题面所示。 之后 n 行，每行包含一个长度为 m 且仅包含 01? 三种字符的字符串。

输出格式

对于每组测试用例，输出一行一个整数，代表最优策略下小杨的得分最多是多少。

输入输出样例

输入 #1

输出 #1

4
2

输入 #2

3
10 11 8
00?01???000
100????000?
01?0????1?0
00?0??101?1
1?0?010?001
???0?00?0?0
?1?0?0000??
00?0?000?00
?000000000?
?0000?000?1
12 5 10
00000
0?000
000?0
00000
00000
000?0
00000
00000
00000
00000
00100
00000
10 12 4
?001?0?00000
1??10???0?10
00?0??0?0??1
00???0?0??11
0??0????0???
???0100???00
??100101????
00??1?1?????
?01??0??0100
1??01?0??0??

输出 #2

15
3
10

输入 #3

4
11 12 7
0?00???0???0
0000?000?01?
?0000??????0
?000000????0
?00?00??0000
0??0000?00?0
0?0?0?0000?1
0001?????000
0??0000??000
?000?1??0?01
??000000????
10 6 8
00?0?0
0010?0
?000??
00????
0000?0
0000?0
??0??0
001???
0?000?
00??00
12 9 7
010101011
110010000
1?1000?1?
001111001
011011101
10??11010
00?100?00
0?110?100
011000??1
1?0?01?10
01000000?
0011?0101
9 9 1
001?00000
000?00000
0000??010
001000000
000010000
110000000
000000000
?00?0000?
000000000

输出 #3

样例 1 解释 对于样例 1 的第二组测试用例，将 （2,1 ）或者 （ 3,3）变成 1 均是最优策略。 数据范围 对于全部数据，保证有 1 \le t \le 10,1 \le n,m \le 500, 1 \le x \le 300 ,同时保证所有测试用例 n\times m 的总和不超过 2.5 \times 10^5。 子任务编号数据点占比tn,mx130\%\le 5\le 10=1230\%\le 10\le 500\le 30340\%\le 10\le 500\le 300

子任务编号	数据点占比	$t$	$n,m$	$x$
$1$	$30\%$	$\le 5$	$\le 10$	$=1$
$2$	$30\%$	$\le 10$	$\le 500$	$\le 30$
$3$	$40\%$	$\le 10$	$\le 500$	$\le 300$

C++ 编辑器

输入

输出

A71636 | 矩阵移动（matrix）

题目描述

输入格式

输出格式

输入输出样例

样例 1 解释

数据范围

A71636 | $矩阵移动（matrix）$

样例 $1$ 解释