P7074 [CSP-J 2020] 方格取数题目描述设有n × m n \times mn×m的方格图每个方格中都有一个整数。现有一只小熊想从图的左上角走到右下角每一步只能向上、向下或向右走一格并且不能重复经过已经走过的方格也不能走出边界。小熊会取走所有经过的方格中的整数求它能取到的整数之和的最大值。输入格式第一行有两个整数n , m n, mn,m。接下来n nn行每行m mm个整数依次代表每个方格中的整数。输出格式一个整数表示小熊能取到的整数之和的最大值。输入输出样例 #1输入 #13 4 1 -1 3 2 2 -1 4 -1 -2 2 -3 -1输出 #19输入输出样例 #2输入 #22 5 -1 -1 -3 -2 -7 -2 -1 -4 -1 -2输出 #2-10说明/提示样例 1 解释样例 2 解释数据规模与约定对于20 % 20\%20%的数据n , m ≤ 5 n, m \le 5n,m≤5。对于40 % 40\%40%的数据n , m ≤ 50 n, m \le 50n,m≤50。对于70 % 70\%70%的数据n , m ≤ 300 n, m \le 300n,m≤300。对于100 % 100\%100%的数据1 ≤ n , m ≤ 10 3 1 \le n,m \le 10^31≤n,m≤103。方格中整数的绝对值不超过10 4 10^4104。2024/2/4 添加一组 hack 数据。C实现#includestdio.hconstintdx[]{1,0,-1},dy[]{0,1,0};typedeflonglongLL;intn,m;boolvis[1005][1005];LL w[1005][1005],f[1005][1005][3],ans-20000000000;inlineLLmx(LL p,LL q){returnpq?p:q;}inlinevoiddfs(intx,inty,intfrom,LL now){if(xnym){ansmx(now,ans);return;}if(f[x][y][from]now)return;elsef[x][y][from]now;for(inti0,xx,yy;i3;i){xxxdx[i];yyydy[i];if(xx1xxnyy1yym!vis[xx][yy]){vis[xx][yy]true;dfs(xx,yy,i,noww[xx][yy]);vis[xx][yy]false;}}}intmain(void){scanf(%d %d,n,m);for(inti1;in;i)for(intj1;jm;j){scanf(%lld,w[i][j]);f[i][j][0]f[i][j][1]f[i][j][2]-20000000000;}vis[1][1]true;dfs(1,1,0,w[1][1]);printf(%lld\n,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容