洛谷 p1219 八皇后
刚参加完蓝桥杯 弱鸡错了好几道。。回头一看确实不难 写起来还是挺慢的
于是开始了刷题的道路
蓝桥杯又名搜索杯 暴力杯。。。于是先从dfs刷起
八皇后是很经典的dfs问题 洛谷的这道题是这样的
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
输入输出格式
输入格式:
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
输出格式:
前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。
输入输出样例
输入样例#1:
6
输出样例#1:
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
弱鸡艰难的写了一个dfs 交一遍之后最后一个测试点没过 应该就是n==13的时候 本地跑了一下确实将近两秒才出来
我的判断条件:
if(m[s][i]==0) { int flag=1; for(x=0;x<n;x++) if(m[x][i]==1) { flag=0; break; } if(flag) for(y=i;y<n;y++) if(m[s+y-i][y]==1&&(s+(y-i)<n)) { flag=0; break; } if(flag) for(y=0;y<i;y++) if(m[s-(i-y)][y]==1&&(s-(i-y)>=0)) { flag=0; break; } if(flag) for(y=0;y<i;y++) if(m[s+(i-y)][y]==1&&(s+(i-y)<n)) { flag=0; break; } if(flag) for(y=i;y<n;y++) if(m[s-(y-i)][y]==1&&(s-(y-i)>=0)) flag=0; if(flag) { m[s][i]=1; f[s]=i+1; dfs(s+1); m[s][i]=0; }
显然写的又笨又蠢。。
瞄一眼题解:
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; int a[100],b[100],c[100],d[100]; int total; int n; int print() { if(total<=2) { for(int k=1;k<=n;k++) cout<<a[k]<<" "; cout<<endl; } total++; } void queen(int i) { if(i>n) { print(); return; } else { for(int j=1;j<=n;j++)//尝试可能的位置 { if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果没有皇后占领,执行以下程序 { a[i]=j;//标记i排是第j个 b[j]=1;//宣布占领纵列 c[i+j]=1; d[i-j+n]=1; //宣布占领两条对角线 queen(i+1);//进一步搜索,下一个皇后 b[j]=0; c[i+j]=0; d[i-j+n]=0; //(回到上一步)清除标记 } } } } int main() { cin>>n; queen(1); cout<<total; return 0; }
其中 a数组表示的是行;b数组表示的是列;c表示的是左下到右上的对角线;d表示的是左上到右下的对角线;
因为对于一个对角线来说 其中的点的i和j是有确定的关系的 所以不必挨个遍历去寻找对角线上有没有其他的皇后 直接把判断的复杂度降低到了O(1)!!
dalao确实是dalao 本弱鸡还是太菜了
相关文章