鸿轩代码找虫
2026-07-30 19:37:15
发布于：广东
你的赛时代码：
#include<iostream>
#include<queue>
using namespace std;
int n,m,k;
int mp[1145][1145];
int vmp[1145][1145] = {0};
int dx[] = {0,1};
int dy[] = {1,0};
struct node{
int x,y,v,ld,t;
};
int bfs(int sx, int sy){
queue<node> q;
q.push({sx,sy,mp[sx][sy],0,0});
vmp[sx][sy] = mp[sx][sy];
int ans = -1;
while(q.size()){
auto cur = q.front();
q.pop();
if(cur.x == n && cur.y == m){
ans = max(ans, cur.v);
continue;
}
for(int i = 0; i < 2; i++){
int xx = cur.x + dx[i], yy = cur.y + dy[i];
if(xx <= n && yy <= m && cur.v + mp[xx][yy] > vmp[xx][yy]){
if(cur.ld == i && cur.t + 1 > k) continue;
int tt = cur.ld == i? cur.t + 1 : 1;
q.push({xx,yy,cur.v + mp[xx][yy],i,tt});
vmp[xx][yy] = cur.v + mp[xx][yy];
}
}
}
return ans;
}
int main(){
freopen("y.in","r",stdin);
freopen("y.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> mp[i][j];
}
}
cout << bfs(1,1);
return 0;
}
这份代码的方向和连续步数已经放进了节点：
struct node{
int x,y,v,ld,t;
};
其中：
ld表示最后移动方向；t表示当前方向连续移动次数。
这部分状态更新是正确的。主要错误出在 vmp 的剪枝。
一、致命错误：vmp 只记录坐标，没有记录方向状态
你定义：
int vmp[1145][1145];
并使用：
if(cur.v + mp[xx][yy] > vmp[xx][yy])
这相当于认为：
到达同一个格子时，只要价值较小，就一定不如价值较大的路径。
这是错误的。
虽然两条路径到达同一个格子，但它们的：
- 最后方向可能不同；
- 连续步数可能不同；
- 后续能够选择的方向也可能不同。
较大价值的路径可能因为连续步数已经达到 而无法继续，较小价值的路径反而能够到达终点。
反例
3 2 1
1 1
1 1
1 1
因为 ，不能连续两次走相同方向。
正确路径是：
下、右、下
路径价值为：
但程序会先处理从起点向右的状态：
(1,1) → (1,2) → (2,2)
到达 时：
- 价值为 ；
- 最后方向是向下；
- 已经连续向下走了 步；
- 因为 ，不能再向下走到终点。
此时：
vmp[2][2] = 3;
随后另一条路径：
(1,1) → (2,1) → (2,2)
也到达 ：
- 价值同样为 ；
- 最后方向是向右；
- 下一步可以向下到达终点。
但你的条件是：
3 > vmp[2][2]
即：
3 > 3
不成立。
因此这个真正能够到达终点的状态被删除，程序最终输出：
-1
正确答案应该是：
4
所以不能使用：
vmp[x][y]
正确状态应该是：
dp[x][y][dir][step]
表示到达 、最后方向为 dir、当前连续走了 step 步时的最大价值。
二、权值为零时，合法路径可能完全无法入队
vmp 是全局数组，初始值全部为 ：
int vmp[1145][1145] = {0};
但转移条件写的是：
cur.v + mp[xx][yy] > vmp[xx][yy]
如果路径价值恰好为 ，就不能进入该格子。
反例
1 2 1
0 0
从 向右一步就可以到达终点，正确答案为：
0
程序开始时：
cur.v = 0;
vmp[1][2] = 0;
判断：
0 + 0 > 0
不成立，因此终点不会入队，最终输出：
-1
即使暂时不考虑方向状态，vmp 也至少应该初始化为 -1 或负无穷，而不能初始化为 。
但是只修改初始化仍然不能解决第一个根本问题。
三、即使价值相等，不同状态也不能删除
你的条件使用严格大于：
cur.v + mp[xx][yy] > vmp[xx][yy]
这会直接删除价值相等的路径。
但价值相等不代表状态相同。
例如上面的反例中，两条路径到达 的价值都为 ，但是：
- 一条最后向下，不能继续向下；
- 另一条最后向右，可以继续向下。
所以不能仅仅把 > 改为 >=。
改成 >= 虽然可能保留部分等价值状态，但仍然无法正确区分：
dir
step
甚至会产生大量重复入队。
根本解决方法仍然是：
dp[x][y][dir][step]
四、当前队列中会存在大量失效节点
当某个格子的 vmp 被更新时，之前已经进入队列的较小价值节点不会被删除。
例如：
q.push({xx,yy,旧价值,...});
之后又出现更大的价值：
vmp[xx][yy] = 新价值;
q.push({xx,yy,新价值,...});
那么队列中两个节点都会继续扩展。
这不会自动导致答案错误，因为节点自身保存了 v、ld 和 t，但会产生许多重复搜索。
而且当前的二维 vmp：
- 有时错误删除有用状态；
- 有时又保留大量旧节点。
因此它既不能正确剪枝，也不能保证良好复杂度。
本题只向右和向下移动，天然是一个有向无环图，不需要 BFS。直接按照行列顺序做 DP 更清晰。
五、连续步数的更新是正确的
你的判断：
if(cur.ld == i && cur.t + 1 > k) continue;
表示：
- 如果继续相同方向；
- 且连续步数会超过 ；
- 就禁止这次移动。
这是正确的。
更新：
int tt = cur.ld == i ? cur.t + 1 : 1;
也正确：
- 方向相同：连续步数加一；
- 方向改变：连续步数重置为一。
初始状态：
q.push({sx,sy,mp[sx][sy],0,0});
虽然把初始方向写成了 0，但初始连续次数为 ：
- 第一次向右得到 ；
- 第一次向下也得到 。
所以这里不会导致错误。
六、起点就是终点时能够正确处理
如果：
N=1，M=1
起点入队后立即满足：
if(cur.x == n && cur.y == m)
于是：
ans = max(ans,cur.v);
能够正确输出：
mp[1][1]
这部分没有问题。
七、数据类型没有问题
一条路径最多经过：
个格子，每个格子最大为 ，最大总价值不超过：
因此：
int v;
int mp[][];
int vmp[][];
都不会溢出。
总结
这份代码主要有两个会直接导致错误的问题：
vmp[x][y]只按照坐标保留最大值，错误删除不同方向、不同连续步数的有用状态。vmp初始化为 ，导致总价值为 的合法路径无法进入队列。
正确状态必须是：
dp[x][y][dir][step]
其中：
x,y：当前位置；dir：最后移动方向；step：当前方向连续移动次数；dp：该状态下能够获得的最大价值。
最关键的错误行就是：
cur.v + mp[xx][yy] > vmp[xx][yy]
因为是否应该保留一个状态，不能只比较它在这个格子上的路径价值，还必须同时考虑最后方向和连续步数。
这里空空如也
有帮助，赞一个