‹ 上一题 下一题 ›

g6-07190. 剪枝位置·进门之前拦 未做

1000 ms 256 MB 测试点 ? 自拟题知识点题GESP-66级·深度优先搜索客观题单选

「限 步内走出迷宫」的数路线程序骨架如下:

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 输出答案之前统一检查一次就够
未选择
输入
输出

            
答案