「限 步内走出迷宫」的数路线程序骨架如下:
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (出界 || 墙 || 来过) continue;
/* 甲 */
total += dfs(nx, ny, step + 1);
/* 乙 */
}
小航想加一条可行性剪枝:「再走一步就要超过 步的这个方向,别递归进去」,即 if (step + 1 > k) continue;。这条判断应该放在( )。
- A. 乙处:递归回来之后再判断,超限的路线不累计进
total - B. 甲处:进入递归之前先拦住——这一步会超 ,连门都不进,整棵子树不生成
- C. 甲、乙两处各写一遍,双保险更稳妥
- D. 甲、乙都不用写,在
main输出答案之前统一检查一次就够