luogo P1219 八皇后

解析

八皇后问题是非常经典的搜索问题。大体思路是依据每行考虑可行列来dfs,但是随着N(行数)增大,
递归的次数会膨胀。所以需要一种合适的精简快捷的判断可行列的方法,这里采用标记数组的方法:
选用3个数组(用check[3]表示),check[0]标记垂直方向,check[1]标记/左下斜方向,check[2]标记
\右下斜方向。
tips: 为什么 i+ji-j+n 可以表示斜标记呢?
不妨自己取方阵行列数尝试(可算得在倾斜方向上,i+j 和 i-j+n 值是固定的)


代码
#include iostream
#include cstdio

using namespace std;

int n,sum=0,cot[15],check[3][35];

void queen(int i){
  if(i == n+1){
    if(sum3){
    for(int k=1;k=n;k++){
      cout cot[k]" ";
    }
        coutendl;
    }
    sum++;
    return;
  }

  for(int j=1;j=n;j++){
    if(  (!check[0][j]) (!check[1][i+j]) (!check[2][i-j+n])  ){ // 判断关键
      cot[i]=j;
      check[0][j] = 1;
      check[1][i+j] = 1;
      check[2][i-j+n] = 1;
      queen(i+1);
      cot[i]=0;
      check[0][j] = 0;
      check[1][i+j] = 0;
      check[2][i-j+n] = 0;
    }
  }
}

int main(){
    cinn;
    queen(1);
    coutsumendl;
    return 0;
}
最新回复(0)
/jishuA_2F2a_2FdM38OFN08hBeX42ZPJcYmdLK1uPuu4evg1dNYc_3D4858358
8 简首页