欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P11248 GESP202409 七级] 矩阵移动 - 洛谷
【题目描述】
小杨有一个n × m n \times mn×m的矩阵，仅包含01?三种字符。矩阵的行从上到下编号依次为1 , 2 , … , n 1,2,\dots, n1,2,…,n，列从左到右编号依次为1 , 2 , … , m 1, 2, \dots, m1,2,…,m。小杨开始在矩阵的左上角( 1 , 1 ) (1,1)(1,1)，小杨只能向下或者向右移动，最终到达右下角( n , m ) (n, m)(n,m)时停止，在移动的过程中每经过一个字符1得分会增加一分（包括起点和终点），经过其它字符则分数不变。小杨的初始分数为0 00分。
小杨可以将矩阵中不超过x xx个字符?变为字符1。小杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。
【输入】
第一行包含一个正整数t tt，代表测试用例组数，接下来是t tt组测试用例。对于每组测试用例，一共n + 1 n + 1n+1行。
第一行包含三个正整数n , m , x n, m, xn,m,x，含义如题面所示。
之后n nn行，每行一个长度为m mm的仅含01?的字符串。
【输出】
对于每组测试用例，输出一行一个整数，代表最优策略下小杨的得分最多是多少。
【输入样例】
2 3 3 1 000 111 01? 3 3 1 000 ?0? 01?【输出样例】
4 2【算法标签】
《洛谷 P11248 矩阵移动》 #动态规划DP# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;string m1[1000];// 存储网格地图，m1[i]表示第i行字符串intt,n,m,dp[505][505][300],k;// t: 测试用例数, n: 行数, m: 列数, k: 最大可使用'?'数intmain(){cin>>t;// 输入测试用例数while(t--){// 输入网格大小和k值cin>>n>>m>>k;// 读入网格，并在每行前添加一个字符，使索引从1开始for(inti=1;i<=n;i++){cin>>m1[i];m1[i]="e"+m1[i];// 在字符串前添加一个字符，使得列索引从1开始}// 初始化动态规划数组为0memset(dp,0,sizeof(dp));// 动态规划计算最大路径for(inti=1;i<=n;i++)// 遍历行{for(intj=1;j<=m;j++)// 遍历列{for(intb=0;b<=k;b++)// 遍历使用的'?'数量{// 情况1：不使用当前位置的'?'（或当前位置是'1'或'0'）// 从上方或左方转移，不消耗'?'名额dp[i][j][b]=(m1[i][j]=='1')+max(dp[i-1][j][b],dp[i][j-1][b]);// 情况2：如果当前位置是'?'，且还有'?'名额可用if(b&&m1[i][j]=='?'){// 将'?'当作'1'，消耗一个'?'名额dp[i][j][b]=max(dp[i][j][b],1+max(dp[i-1][j][b-1],dp[i][j-1][b-1]));}}}}// 在所有可能的'?'使用数量中，找到最大价值intans=0;for(inti=0;i<=k;i++){ans=max(ans,dp[n][m][i]);}cout<<ans<<endl;}return0;}【运行结果】
2 3 3 1 000 111 01? 4 3 3 1 000 ?0? 01? 2
