芊宇代码找虫
2026-07-30 19:33:09
发布于：广东
总体结论
这份代码在逻辑上可以正确枚举所有合法路径，cnt 的回溯、连续方向步数的更新也基本正确。
真正致命的问题是：
DFS 枚举了每一条合法路径，时间复杂度是指数级，会严重超时。
一、致命错误：DFS 枚举所有路径
你每遇到一个可以移动的方向，就继续递归：
for (int i = 0;i < 2;i++)
{
...
dfs(...);
}
这相当于把所有从 到 的合法路径全部走一遍。
当 足够大时，连续步数限制不起作用，路径数量为：
当 时，路径数量是：
这是一个接近 量级的数，根本无法枚举。
所以这份程序可能通过：
- ；
- 等路径很少的数据；
但面对一般的 数据一定超时。
正确复杂度应当是：
需要使用动态规划：
dp[i][j][dir][step]
表示到达 时，最后移动方向为 dir，已经连续移动 step 步的最大价值。
二、vis 数组没有实际作用
你定义：
bool vis[N][N];
并且初始化：
vis[1][1] = 1;
判断时使用：
if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] != 0)
continue;
但是递归过程中没有执行：
vis[nx][ny] = 1;
所以除起点之外，其他位置的 vis 永远是 false。
实际上，本题只能向右或向下移动，不可能形成环，因此根本不需要 vis。
可以直接删除：
bool vis[N][N];
vis[1][1] = 1;
vis[nx][ny] != 0
注意
不能简单地“修复”为：
vis[nx][ny] = 1;
并且永久不撤销。
因为同一个格子必须允许通过不同路径、不同方向状态到达。全局标记访问会错误删除其他可能更优的路径。
即使写成路径内标记并回溯，也没有必要，因为只向右、向下本来就不会回到原格子。
三、连续步数判断本身基本正确
你写了：
void dfs(node now,int step,int di)
{
if (step > k) return;
这里的 step 表示当前方向已经连续移动的次数。
继续相同方向时：
dfs({nx,ny},step + 1,i);
切换方向时：
dfs({nx,ny},1,i);
这是正确的。
初始调用：
dfs({1,1},0,-1);
因为第一次移动时 i != -1，所以会进入：
dfs({nx,ny},1,i);
第一步计数为 ，也正确。
不过可以提前剪掉非法移动，避免进行一次无意义递归：
if (i == di && step == k) continue;
当前写法不会算错，只是会先加入格子价值、递归进去，再因为 step > k 返回。
四、cnt 的回溯写法正确
你使用：
cnt += w[nx][ny];
dfs(...);
cnt -= w[nx][ny];
这表示：
- 进入下一格时加入价值；
- 搜索这条路径；
- 返回后撤销价值。
对于单线程 DFS 枚举路径来说，这种写法是正确的。
起点也只加入了一次：
cnt = w[1][1];
不存在起点重复计算的问题。
五、终点处理正确
你写的是：
if (now.x == n && now.y == m)
{
ans = max(ans,cnt);
return;
}
这是正确的终点判断。
而且没有在第一次到达终点时结束整个 DFS，因此能够比较所有路径的答案。
六、无解输出正确
初始化：
ll cnt,ans = -1;
只有合法到达终点时才更新：
ans = max(ans,cnt);
因为所有格子权值都非负，所以合法答案一定不小于 。
如果不存在合法路径，ans 会保持为 -1，符合题意。
七、 也能正确处理
当起点就是终点时：
cnt = w[1][1];
dfs({1,1},0,-1);
进入 DFS 后立即满足：
now.x == n && now.y == m
因此：
ans = w[1][1];
这部分没有问题。
八、freopen 是否保留取决于评测方式
题目明确写了：
输入文件：y.in
输出文件：y.out
因此在原题评测环境中：
freopen("y.in","r",stdin);
freopen("y.out","w",stdout);
通常可以保留。
但若复制到普通在线评测环境测试，则可能需要删除，否则会因为找不到文件而读不到输入。
错误总结
| 位置 | 判断 |
|---|---|
| DFS 枚举每条路径 | 致命错误，指数复杂度，TLE |
vis |
没有实际作用，应删除 |
| 连续方向计数 | 正确 |
方向切换后变为 1 |
正确 |
cnt 加减回溯 |
正确 |
| 终点判断 | 正确 |
无解输出 -1 |
正确 |
| 正确 |
这份代码不是答案算错，而是：
通过暴力枚举能够得到正确答案，但最大数据下完全跑不完。
必须把大量重复的 DFS 状态合并为：
只保留每个状态的最大价值。
这里空空如也
有帮助，赞一个