‹ 上一题 下一题 ›

g6-07174. 剪枝·皇后棋盘的隐形剪刀 未做

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

N 皇后逐行放皇后,用三个标记数组提前堵冲突:col[c] 记列、d1[row-c+n] 记主对角线、d2[row+c] 记副对角线。枚举本行每一列之前先判断:

if (col[c]) continue; if (d1[row-c+n]) continue; if (d2[row+c]) continue;

对这三个判断的作用,理解正确的是( )。

  • A. 只是为了让代码读起来清楚,对搜索量没有影响
  • B. 加了这三个判断后,N 皇后的复杂度从指数级降到了多项式级
  • C. 这三个判断属于记忆化:把放过皇后的位置存进数组,下次直接查
  • D. 这三个判断就是剪枝:同列、同对角线的候选在递归发生之前就被跳过,放不下皇后的分支一个都不会真去试
未选择
输入
输出

            
答案