鸿泽代码找虫

吴老师

2026-07-30 19:26:39

发布于：广东

26阅读

0回复

0点赞

一、最严重的错误：`cnt` 只按坐标记录

你写的是：

ll cnt[1005][1005];

以及：

cnt[nx][ny] = cnt[u.x][u.y] + a[nx][ny];

但是到达同一个格子时，可能存在不同状态：

最后向右连续走了若干步；
最后向下连续走了若干步。

这些状态对应的路径价值不同，不能共用同一个：

cnt[x][y]

反例

2 3 1
0 1 0
100 0 0

因为 $K=1$ ，不能连续走两次相同方向。

正确的唯一合法路径是：

右、下、右

路径价值为：

$0+1+0+0=1$

另一种走法：

下、右、右

最后连续向右两次，不合法。

你的代码执行过程

先处理向右路径：

(1,1) → (1,2) → (2,2)

于是：

cnt[2][2] = 1;

此时入队的状态是：

最后一步向下

所以它下一步可以向右。

然后处理向下路径：

(1,1) → (2,1) → (2,2)

于是：

cnt[2][2] = 100;

把原来的 1 覆盖了。

接下来，队列中第一条状态被取出。它的方向状态是：

右、下

所以允许继续向右。

但它读取的价值却是：

cnt[2][2] = 100

也就是另一条路径的价值。

最终程序会拼接出一个不存在的状态：

使用“下、右”路径的价值，搭配“右、下”路径的方向。

于是可能输出 100，而正确答案是 1。

所以路径价值必须和方向、连续步数一起记录。

正确状态应该是：

dp[x][y][direction][step]

而不是：

cnt[x][y]

二、队列会枚举所有合法路径，复杂度指数级

你没有对相同状态进行合并：

q.push({nx,ny,...});

只要有一条合法路径到达某个位置，就会产生一个新的队列节点。

而从左上角到右下角的路径数量可能非常多。

不考虑连续步数限制时，路径数量是：

$\binom{N+M-2}{N-1}$

当 $N=M=500$ 时，这个数极其巨大。

即使有 $K\le 10$ 的限制，合法路径数量仍然可能是指数级的。

因此这份程序会：

队列中出现大量重复状态；
时间复杂度远远超过限制；
甚至可能内存溢出。

本题不能枚举每一条路径，必须把相同状态合并，只保留最大价值。

状态数量只有：

$O(NMK)$

三、`N=M=1` 时答案错误

当起点就是终点时：

N=1，M=1

不需要进行任何移动，答案应该是：

a[1][1]

但你的代码中：

ll ans = -1;

只有移动进入终点时才更新：

if(nx == n && ny == m){
    ans = max(ans,cnt[nx][ny]);
}

当起点本身就是终点时，循环中不会产生任何移动，因此最终输出：

-1

应该单独处理：

if(n == 1 && m == 1){
    cout << a[1][1];
    return 0;
}

四、边界判断用了按位或 `|`

你写的是：

if(nx<1||ny<1||nx>n|ny>m) continue;

其中：

nx > n | ny > m

使用的是按位或 |，应该写成逻辑或 ||：

if(nx < 1 || ny < 1 || nx > n || ny > m) continue;

由于两个比较结果恰好都是 0 或 1，这份代码中通常仍能得到类似逻辑或的结果，所以它不一定立刻导致错误，但这是明显的运算符误用。

五、`vis` 完全没有使用

你定义了：

bool vis[1005][1005];

并且只写了一次：

vis[1][1] = 1;

后续既不检查，也不更新其他位置，因此这个数组没有任何作用。

不过本题也不能使用普通的：

vis[x][y]

因为同一个格子可以由不同方向、不同连续步数到达。

如果使用访问标记，也至少应该与完整状态对应：

vis[x][y][direction][step]

但本题更适合直接使用 DP，不需要 BFS 的 vis。

六、你的方向计数部分基本正确

你的方向定义：

int dx[] = {0,1};
int dy[] = {1,0};

所以：

i=0 表示向右；
i=1 表示向下。

检查：

if(u.dir[i] + 1 > k) continue;

表示如果继续当前方向会超过 $K$ ，就不能走，这部分是正确的。

向右时：

q.push({nx,ny,{u.dir[0]+1,0}});

表示：

向右次数加一；
向下次数清零。

向下时：

q.push({nx,ny,{0,u.dir[1]+1}});

表示：

向右次数清零；
向下次数加一。

这部分关于连续步数的更新逻辑没有问题。

问题在于：你只把方向次数放进了状态，却没有把对应的路径价值也放进状态。

七、即使把价值放入队列，仍然会超时

你可能会想到修改结构体：

struct stu{
    ll x, y;
    ll dir[2];
    ll value;
};

然后入队：

q.push({nx, ny, ..., u.value + a[nx][ny]});

这样可以解决不同路径价值互相覆盖的问题。

但是仍然会枚举所有合法路径，复杂度还是指数级，最大数据一定无法通过。

所以不能只把 value 加入队列，必须做状态合并：

对相同的 $(x,y,d,t)$ ，只保留最大价值。

八、正确状态

定义：

dp[i][j][0][t]

表示到达 $(i,j)$ ，最后连续向右走了 $t$ 步时的最大价值。

定义：

dp[i][j][1][t]

表示到达 $(i,j)$ ，最后连续向下走了 $t$ 步时的最大价值。

其中：

$1\le t\le K$

向右继续走

如果之前也是向右：

dp[i][j][0][t]
=
dp[i][j-1][0][t-1]+a[i][j]

从向下切换为向右

dp[i][j][0][1]
=
\max_t dp[i][j-1][1][t]+a[i][j]

向下继续走

dp[i][j][1][t]
=
dp[i-1][j][1][t-1]+a[i][j]

从向右切换为向下

dp[i][j][1][1]
=
\max_t dp[i-1][j][0][t]+a[i][j]

九、这份代码的错误等级总结

位置	问题	结果
`cnt[nx][ny]`	不同状态共用同一个价值	WA
队列枚举所有路径	没有合并重复状态	TLE/MLE
`ans=-1`	没处理 $N=M=1$	WA
`nx>n	ny>m`	使用按位或而不是逻辑或	写法错误
`vis`	除起点外完全没用	冗余
`dir[2]` 更新	切换方向清零	这一部分正确