这份代码的复数加法、乘法公式和输出格式基本都对,真正导致错误的是:你使用 queue 保存“当前答案”,但没有保证队列中始终只有一个复数。
错误一:初始答案没有放入队列
题目规定计算器初始答案是:
0+0i0+0i 0+0i
但你的队列初始为空:
如果第一条指令是 k=2 或 k=3,就会执行:
此时队列为空,访问 front() 会产生未定义行为。
例如:
正确过程应为:
(0+0i)+(1+2i)=1+2i(0+0i)+(1+2i)=1+2i (0+0i)+(1+2i)=1+2i
正确输出:
但你的程序会直接访问空队列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
错误二:执行 K=1 时没有删除旧答案
k=1 表示把当前答案替换为 x+yix+yix+yi。
你的代码只是把新答案压入队列:
却没有删除队列中原来的答案。
例如:
正确过程:
第一条:
1+1i1+1i 1+1i
第二条直接覆盖:
2+2i2+2i 2+2i
第三条相加:
(2+2i)+(1+1i)=3+3i(2+2i)+(1+1i)=3+3i (2+2i)+(1+1i)=3+3i
正确输出:
但是你的队列变化为:
第三次执行 k=2 时,你取出的是最前面的旧答案:
于是算出:
(1+1i)+(1+1i)=2+2i(1+1i)+(1+1i)=2+2i (1+1i)+(1+1i)=2+2i
错误输出为:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
乘法部分是正确的
设当前答案为:
a+bia+bi a+bi
乘数为:
x+yix+yi x+yi
则:
(a+bi)(x+yi)=(ax−by)+(ay+bx)i(a+bi)(x+yi)=(ax-by)+(ay+bx)i (a+bi)(x+yi)=(ax−by)+(ay+bx)i
你的代码:
此时:
因此:
ans1=ax−byans1=ax-by ans1=ax−by
ans2=ay+bxans2=ay+bx ans2=ay+bx
乘法公式没有问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
输出格式也是正确的
你的判断:
可以正确输出:
虚部为负数时,b 本身会输出负号,因此不能再输出 +,这一点你处理正确。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最合适的修改方法
这道题只需要两个变量保存当前实部和虚部,不需要队列:
结论
会导致错误的地方只有两个核心问题:
1. 队列没有初始化为题目规定的 0+0i0+0i0+0i。
2. k=1 时没有清除旧答案,连续出现赋值操作后会读取到过期数据。
乘法公式、加法公式和正负号输出方式都是正确的。
异星矿区
一、最先出现的错误:CHECK 的判断写反了
你的 check:
含义是:
* 返回 true:坐标合法,并且没有访问过;
* 返回 false:越界或者已经访问过。
但你在 BFS 中写的是:
这相当于:
> 如果下一个格子合法,就不走。
应该至少改成:
样例 1 的执行过程
从 (1,1)(1,1)(1,1) 出发:
* 向下到 (2,1)(2,1)(2,1),合法,check 返回 true,于是 continue;
* 向右到 (1,2)(1,2)(1,2),合法,check 返回 true,于是 continue。
两个合法方向全部被跳过,队列清空。
因此只统计了:
而且你输出了两次 ans:
所以样例 1 会输出:
而不是 16。
不过,即使把这一行改正确,整个算法仍然不能解决本题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、根本错误:本题不能使用普通 BFS
你使用:
并且每个节点只记录:
但本题到达一个格子时,还必须知道:
* 最后一次移动的方向;
* 这个方向已经连续走了多少步;
* 当前路径收集到的价值。
例如 K=2K=2K=2,到达同一个格子时可能存在:
* 最后连续向右走了 222 步;
* 最后连续向右走了 111 步;
* 最后连续向下走了 222 步;
* 最后连续向下走了 111 步。
这些状态的后续行动能力不同,不能只记录坐标。
例如:
* 连续向右走了 222 步,下一步不能再向右;
* 连续向右走了 111 步,下一步还可以向右。
所以状态至少应该包含:
而不只是:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、VIS[N][N] 的设计错误
你写的是:
表示某个格子一旦访问过,就永远不能再次访问。
但同一个格子可能需要被不同状态到达。
例如:
这两个状态虽然位置一样,但完全不同。
如果状态 A 先把:
那么状态 B 就不能再进入这个格子,可能丢失最优答案。
所以不能使用:
正确的状态应类似:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、ANS += G[NX][NY] 不是一条路径的价值
你使用一个全局变量:
每访问一个格子就执行:
但 BFS 会同时搜索多条分支。
例如从起点可以:
* 向下进入 (2,1)(2,1)(2,1);
* 向右进入 (1,2)(1,2)(1,2)。
这两个格子不一定属于同一条路径,但你的代码会把两个格子的价值都加入 ans。
也就是说,你计算的是:
> BFS 总共访问过的所有格子的价值之和。
题目要求的是:
> 某一条从起点到终点的合法路径的最大价值。
每一种状态都应该保存自己的路径价值,而不是使用一个全局 ans。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、终点判断比较错了
你写的是:
这里比较的是:
而不是判断当前位置是不是终点。
假如某个中间格子的矿石价值恰好和终点相同,程序就会错误地认为到达了终点。
应该判断坐标:
但是即使改成坐标判断,也不能第一次到终点就直接 return。
因为第一次到达终点的路径,不一定是价值最大的路径。
BFS 只能保证步数层次,但本题所有合法路径的总步数其实都相同,都是:
(N−1)+(M−1)(N-1)+(M-1) (N−1)+(M−1)
第一次到达终点与最大价值没有必然关系。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、JB 没有记录每条路径的连续步数
你定义:
但实际上只使用了:
因为:
中的 i 只有 000 和 111。
所以整个 jb 数组实际上只用了两个位置:
* jb[0][0];
* jb[1][1]。
你似乎想让它们分别表示:
* 连续向下的次数;
* 连续向右的次数。
但这是全局变量,所有 BFS 分支共享。
例如队列中有两条不同路径:
* 路径 A 连续向下走了 222 步;
* 路径 B 连续向右走了 111 步。
处理路径 A 时修改 jb,会影响路径 B。
连续步数应该属于某一条具体路径或状态,不能全局共享。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、方向切换时没有正确重置步数
正确规则是:
* 继续相同方向:连续步数加 111;
* 改变方向:新方向连续步数变成 111。
例如移动序列:
最后向右的连续步数是 111。
但你的代码只是:
没有在正常切换方向时把另一个方向的计数清空。
因此可能出现:
* 曾经向下走过 222 步;
* 后来已经转向右;
* jb[0][0] 仍然保留为 222。
这不是“连续向下 222 步”,只是历史上向下走过 222 步。
题目限制的是连续次数,不是累计次数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、把连续步数限制写死成了 2
这里:
以及:
使用了固定值:
但题目中的限制是输入的:
KKK 可能是 111 到 101010 中的任意值。
因此写死为 2 肯定错误。
不过即使将 2 改成 k,这里的贪心策略仍然错误。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、比较相邻格子价值的贪心错误
你写了:
这里是在比较两个可能方向的格子价值,优先选择当前价值更大的格子。
但本题不能贪心。
例如:
当前位置看到:
* 向右价值为 100;
* 向下价值为 10。
局部看应该选择 100,但走向 10 的路径以后可能得到 1000,最终总价值更大。
此外,连续移动限制也可能导致:
* 当前较大的格子后面无法合法到达终点;
* 当前较小的格子反而能走出更优合法路径。
所以不能只比较下一格的大小。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、对逻辑矩阵之外的位置进行了访问
例如:
当 ny == m 时,访问的是:
以及:
当 nx == n 时,访问的是:
虽然你的数组开到了 505,在部分情况下不会立即发生物理越界,但这些格子不属于题目给出的矩阵。
全局数组默认初始化为 000,这会导致程序拿不存在的格子价值参与比较。
更严重的是,因为你的 check 判断写反,程序可能把越界位置加入队列:
然后继续从越界位置向下或向右扩展,最终可能发生真正的数组越界。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、这些 CHECK 条件的逻辑相反
例如:
check(...) == true 表示下一个位置合法且未访问。
也就是说这段代码实际含义是:
> 连续步数等于 KKK,并且另一个位置可以走,于是直接判定失败并结束程序。
这明显不合理。
而且某个节点的某个方向不能走,并不代表整个问题无解。
队列中可能还有其他节点可以到达终点,所以不能直接:
最多只能放弃当前这个转移:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十二、下面这个无解判断没有依据
nx+1>n 且 ny+1>m 不能说明无法到达终点。
是否无解应该通过最终状态判断:
> 是否存在任意合法状态到达 (N,M)(N,M)(N,M)。
不能因为某个局部状态走不动,就直接认为所有路径都无解。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十三、FLAG 实际没有发挥作用
你设置了:
或者:
但最后对应的输出被注释掉了:
当前程序始终输出:
所以即使判定无解,也不会输出 -1。
而且 flag 本身的判定方式也是错误的:
* 某个方向走不了,不代表整体无解;
* 某个格子价值等于终点价值,不代表到达终点。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十四、输出了两遍答案
bfs() 最后:
main() 中又写:
所以答案会连续输出两遍。
例如答案是 16,可能输出:
应该只保留一次输出。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十五、起点等于终点的情况也会被错误处理
当:
起点就是终点,正确答案应该是:
你的代码会执行:
虽然恰好会返回,但这是因为价值相等,而不是正确判断坐标。
此外仍然会在 main 中输出一次,行为只是碰巧正确。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十六、这份代码不能通过局部修改变正确
即使你修改以下内容:
并把终点判断改成:
仍然有三个无法修补的根本问题:
1. vis[i][j] 无法表示不同方向和不同连续步数;
2. jb 是全局计数,无法表示每条路径的状态;
3. ans += g[nx][ny] 会把多条分支的价值加在一起。
所以整体必须改成动态规划。
正确状态应为:
dp[i][j][d][t]dp[i][j][d][t] dp[i][j][d][t]
其中:
* (i,j)(i,j)(i,j):当前位置;
* ***:最后移动方向;
* ttt:当前方向连续移动步数;
* 状态值:到达这里能获得的最大价值。
这份代码最核心的错误可以总结为:
> 你把“每一条路径自己的方向、连续步数和价值”,全部写成了全局变量。这样不同路径的状态会互相干扰,因此无法得到正确答案。