题号1219
感觉写的非常满意……哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
n=13都不用打表啦！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include<string> #include<cstring> #include<algorithm> #include<cstdlib> #include<iostream> using namespace std; int n; int cnt;//情况计数器 bool line[14],row[14],left_diagonal[26],right_diagonal[26]; //占用情况数组：行；列；左上-右下对角线；右上-左下对角线 int pos[14]; //记录每一行的棋子放在哪一列 inline int calculate_left_dia(int x,int y){//计算x行y列的棋子在第几个左上-右下对角线上 return x+y-1; } inline int calculate_right_dia(int x,int y){//计算x行y列的棋子在第几个右上-左下对角线上 return (n+1-x)+y-1; } void search(int level){//dfs搜索：行 if(level==n+1){//递归基 cnt++; if(cnt>3)return; for(int i=1;i<=n;i++){//输出结果 cout<<pos[i]<<" "; } cout<<endl; } for(int i=1;i<=n;i++){//遍历列 if(!line[i]&&!row[i]&&!left_diagonal[calculate_left_dia(level,i)]&&!right_diagonal[calculate_right_dia(level,i)]){//满足要求 pos[level]=i; line[i]=true;row[i]=true; left_diagonal[calculate_left_dia(level,i)]=true; right_diagonal[calculate_right_dia(level,i)]=true; search(level+1);//继续深搜 line[i]=false;row[i]=false;//回溯 left_diagonal[calculate_left_dia(level,i)]=false; right_diagonal[calculate_right_dia(level,i)]=false; } } } int main(){ cin>>n; search(1); cout<<cnt; } |