AI题库 · GESP-C++七级题库
题目分享 #20862
矩阵移动
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个有一个 n×m 的矩阵,仅包含 01? 三种字符。矩阵的行从上到下编号依次为1,2,...,n,列从左到右编号依次为1,2,...,m 编号。小杨开始在矩阵的左上角(1,1),小杨只能向下或者向右移动,最终到达右下角(n,m)时停止,在移动的过程中每经过一个字符 1 得分会增加一分(包括起点和终点),经过其它字符则分数不变。小杨的初始分数为 0 分。
小杨可以将矩阵中不超过 x 个字符 ? 变为字符 1。小杨在修改矩阵后,会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。
输入格式
第一行包含一个正整数 t ,代表测试用例组数。
接下来是 t 组测试用例。对于每组测试用例,一共 n+1 行。
第一行包含三个正整数n,m,x,含义如题面所示。
之后 n 行,每行包含一个长度为 m 且仅包含 01? 三种字符的字符串。
输出格式
对于每组测试用例,输出一行一个整数,代表最优策略下小杨的得分最多是多少。
输入样例
2
3 3 1
000
111
01?
3 3 1
000
?0?
01?输出样例
4
2对于第二组测试用例,将(1,1)或者 (3,3)变成 1 均是最优策略。

对于全部数据,保证有1≤t≤10,1≤n,m≤500,1≤x≤300,同时保证所有测试用例 n×m 的总和不超过 2.5×105。
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。