蓝桥杯ALGO-125算法训练 王、后传说(回溯、递归)

问题描述
  地球人都知道,在国际象棋中,后如同太阳,光芒四射,威风八面,它能控制横、坚、斜线位置。
看过清宫戏的中国人都知道,后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围,但也总能找到相安无事的办法。
所有中国人都知道,皇权神圣,伴君如伴虎,触龙颜者死……
现在有一个n*n的皇宫,国王占据他所在位置及周围的共9个格子,这些格子皇后不能使用(如果国王在王宫的边上,占用的格子可能不到9个)。当然,皇后也不会攻击国王。
现在知道了国王的位置(x,y)(国王位于第x行第y列,x,y的起始行和列为1),请问,有多少种方案放置n个皇后,使她们不能互相攻击。
输入格式
  一行,三个整数,皇宫的规模及表示国王的位置
输出格式
  一个整数,表示放置n个皇后的方案数
样例输入
8 2 2
样例输出
10
数据规模和约定
  n<=12

分析:和n皇后问题一样,一样的套路…..加一个判定当前是否为国王的领地就可以~
pos[i]存放的是第i行的皇后所在的位置
递归以行的形式递归,每次放置的皇后要判断是否与前面已经放置的皇后冲突
从pos[row] = 0开始一直到n-1,判断是否安全 如果安全就进行下一行的摆放
每次递归到row==n的时候表示当前所有n个皇后已经摆放完成
这是一个深度优先的过程,从在第一行放在第一个位置开始,摆放第二行、第三行…直到最后一行。
然后pos[row]++,表示将第一行放在第二个位置…然后摆放第二行、第三行…直到最后一行……
直到所有的情况深度优先搜索完成。