题目背景

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

题目描述

给定一个 $n imes m$ 的矩阵，元素只可能是 0、1、?。小杨从左上角 $(1,1)$ 出发，只能向下或向右移动，最终到达右下角 $(n,m)$。路径上每经过一个字符 1，得分增加 $1$（包括起点和终点），经过其他字符不得分。

在出发前，小杨可以将矩阵中不超过 $x$ 个 ? 改成 1。请问修改后再选择最优路径，最多能得到多少分。

输入格式

第一行输入正整数 $t$，表示测试组数。 每组数据第一行输入三个正整数 $n,m,x$。 接下来 $n$ 行，每行输入一个长度为 $m$、仅包含 0、1、? 的字符串。

输出格式

对每组数据输出一行一个整数，表示最多得分。

1
2 2 1
0?
10

1

数据范围与提示

• $1 \le t\le 10$。
• $1 \le n,m \le 500$，$0 \le x\le 300$。
• 只能把 ? 改成 1，不要求用完全部修改次数。

来源

GESP 2024 年 09 月 C++ 七级 T2